Prove $\binom{2n}{n}~=~\sum_{k=0}^n \binom{n}{k}^2$

Question

Within another answer to a question concerning a sums of the type

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

there was a simple indetity given which reduces this sum to a simple binomial coefficient, to be exact to

$$\binom{2n}{n}$$

However I tried to prove the formula

$$\sum_{k=0}^n \binom{n}{k}^2~=~\binom{2n}{n}$$

by induction and failed. Overall my attempt was to split up the sum for $n=m+1$ as follows

$$\sum_{k=0}^{m+1} \binom{m+1}{k}^2~=~\sum_{k=0}^m \binom{m+1}{k}^2 + \binom{m+1}{m+1}^2~=~(m+1)^2\sum_{k=0}^m \frac1{(m+1-k)^2}\binom{m}{k}^2 +1$$

I now stuck at reshaping this sum in the end and to substitute it by

$$\binom{2m}{m}$$

so I guess either induction is not the right way to approach to this proof or I made a critical error somewhere. I would be interested in a right proof and a explanation why my attempt did not worked out.

Thank you in advance.

---

I just figured out this formula is called Vandermondes Identity and it can be derived in way from the Binomial Theorem. But I am still interested in a proof maybe without this property.

Answer 1

EDIT: After posting, I saw the edit to the question asking for a proof without using the binomial theorem. Unfortunately, I don't have one, but I'll leave this answer posted since it is a correct proof.

Look at the coefficient of $x^n$ in the expansion of $(1+x)^{2n}.$ By the binomial theorem, we have $$(1+x)^{2n} = \sum^{2n}_{k=0} \binom{2n}{k} x^k$$ and thus the coefficient of $x^n$ is $\binom{2n}n$. On the other hand, we have $$(1+x)^{2n} = \big((1+x)^n\big)^2 = \left(\sum^n_{\ell=0} \binom{n}\ell x^\ell \right)^2.$$ When we square this sum, the terms that produce $x^n$ are those of the form $x^\ell\cdot x^{n-\ell}$ and the corresponding coefficient is $\binom n \ell \binom{n}{n-\ell}$. But $\binom n \ell = \binom{n}{n-\ell}$, so these coefficients are $\binom{n}\ell^2$. Since one of these occur for each $\ell=0,\ldots,n$, we see that the whole coefficient of $x^n$ is $\sum^n_{\ell=0} \binom{n}{\ell}^2$ and thus $$\binom{2n}n = \sum^n_{\ell=0} \binom n \ell^2.$$

Answer 2

Suppose you have a set of size $2n$. Divide it into two subsets of size $n$. You know that $2n\choose n$ is the number of subsets of size $n$ from the $2n$ elements.

Let $k$ be an integer $0 \le k \le n$. Let $E_k$ be the set of all subsets of size $n$ where $k$ are chosen from one of the two subsets of size $n$ and $n-k$ from the other. Then $E_k$ has $${n\choose n-k}{n\choose k} = {n\choose k}^2$$ elements. I think you can see the rest.

Answer 3

Maybe it is interesting to see that using the integral representation of the binomial coefficient $$\dbinom{n}{k}=\frac{1}{2\pi i}\oint_{\left|z\right|=\epsilon}\frac{\left(1+z\right)^{n}}{z^{k+1}}dz$$ we get $$\sum_{k=0}^{n}\dbinom{n}{k}^{2}=\frac{1}{2\pi i}\oint_{\left|z\right|=\epsilon}\frac{\left(1+z\right)^{n}}{z}\sum_{k=0}^{n}\dbinom{n}{k}z^{-k}dz$$ $$=\frac{1}{2\pi i}\oint_{\left|z\right|=\epsilon}\frac{\left(1+z\right)^{n}}{z}\left(1+\frac{1}{z}\right)^{n}dz=\frac{1}{2\pi i}\oint_{\left|z\right|=\epsilon}\frac{\left(1+z\right)^{2n}}{z^{n+1}}dz=\dbinom{2n}{n}.$$

Answer 4

Let there be a square grid of size $n$ x $n$ with two particles situated at the opposite corners. We want to find the no. of ways they can meet if both of them have the same speed and they can move only up and down as they both have to cover equal distance they must meet on the diagonal. So number of ways of meeting is $$\sum_{r=0}^{r=n} {\binom{n}{r}}^2$$ and other way of evaluating this will to be to see the one particle from the other particle's frame: it has to travel n units up and n units right and number of ways of doing it will be: $$\binom{2n}{n}$$