0
$\begingroup$

How can I prove the following statement?

$$\binom{n}{0} ^2 + \binom{n}{1} ^2 + \binom{n}{2} ^2 + ... + \binom{n}{n} ^2 = \binom{2n}{n}$$

I know that:

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

But I don't see how I could use it to prove the given problem.

$\endgroup$
3
7
$\begingroup$

Note that \begin{eqnarray*} (1+x)^{2n} & = & (1+x)^{n}(1+x)^{n}\\ & = & \left[\sum_{i=0}^{n}\binom{n}{i}x^{i}\right]\left[\sum_{j=0}^{n}\binom{n}{j}x^{j}\right] \end{eqnarray*} Expand the right hand side and observe that the $x^{n}$ term is \begin{eqnarray*} & & \binom{n}{0}x^{0}\cdot\binom{n}{n}x^{n}+\binom{n}{1}x^{1}\cdot\binom{n}{n-1}x^{n-1}+\ldots+\binom{n}{n-1}x^{n-1}\cdot\binom{n}{1}x^{1}+\binom{n}{n}x^{n}\cdot\binom{n}{0}x^{0}\\ & = & \left[\sum_{i=0}^{n}\binom{n}{i}\binom{n}{n-i}\right]x^{n}\\ & = & \left[\sum_{i=0}^{n}\binom{n}{i}\binom{n}{i}\right]x^{n}. \end{eqnarray*} The $x^{n}$ in the left hand side is just $\binom{2n}{n}x^{n}$. Therefore $\sum_{i=0}^{n}\binom{n}{i}^{2}=\binom{2n}{n}$.

$\endgroup$