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

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.

• It is a particular case of Vandermonde's identity (aka the Chu--Vandermonde identity), which states that $\dbinom{x+y}{n} = \sum\limits_{k=0}^n \dbinom{x}{k}\dbinom{y}{n-k}$ for any nonnegative integer $n$ and any reasonable $x$ and $y$ (these can be commuting indeterminates, or just real numbers). For two proofs that don't use the binomial theorem, see the proofs of Theorem 2.27 in Darij Grinberg, Notes on the combinatorial fundamentals of algebra, version of 26 April 2018. – darij grinberg Jul 24 '18 at 13:11

## 4 Answers

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.$$

• Ah, thank you. That is a quite elegant way to prove this. – mrtaurho Jul 23 '18 at 13:24

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}.$$

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}$$

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.