What is the asymptotic order of $\sum_{k=0}^n {n\choose k}^2$?

Question

What is the asymptotic order of $\sum_{k=0}^n {n\choose k}^2$? That is, find $g(n)$ such that $$\lim_{n\to \infty}\frac{\sum_{k=0}^n {n\choose k}^2}{g(n)}=1$$

We can expand the binomial coefficient and use Stirling's approximation but I can not determine g(n).

Answer 1

This is a comment regarding the comment of Probability student:

According to Wolfy,

$\sum_{k=0}^n({n \choose k}{n+1\choose k}) = \dfrac{2^{2n+1}(n + 1/2)!}{\sqrt{π} (n + 1)!} $

$\sum_{k=0}^n({n \choose k}{n+2\choose k}) = \dfrac{2^{2n + 2} (n + 1) (n + 1/2)!}{\sqrt{π} (n + 2)!} $

Looks like it might be possible to get a closed form for $\sum_{k=0}^n({n \choose k}{n+m\choose k})$.

And Wolfy says that $\sum_{k=0}^n({n \choose k}{n+m\choose k}) =\dfrac{(m + 2 n)!}{n! (m + n)!} $.

Answer 2

$$\sum_{k=0}^n \binom{n}{k}\binom{n+m}{k} = \sum_{k=0}^n \binom{n}{n-k}\binom{n+m}{k}.$$

This counts the number of ways to choose $n$ objects from a set of $2n+m$. To see this, let there be $n$ red ones and $n+m$ blue ones, and do casework on how many red and how many blue we choose. So:

$$\sum_{k=0}^n \binom{n}{k}\binom{n+m}{k} = \binom{2n+m}{n}.$$

I think, using Stirling's formula, you can probably do the rest.

Answer 3

If you use marty cohen's answer, taking the logarithm and then using Stirling approximation, you should get something like $$\log \left(\frac{(m+2 n)!}{n! (m+n)!}\right)=2 n \log (2)+\log \left(\frac{2^m}{\sqrt{\pi n}}\right)-\frac{2 m^2+2 m+1}{8 n}+O\left(\frac{1}{n^2}\right)$$ and then, for large values of $n$, $$\frac{(m+2 n)!}{n! (m+n)!} \sim \frac{2^{2n+m}} {\sqrt{\pi n}}$$ What is interesting (at least to me) is the next term which shows how is approached the asymptotics.