Binomial Coefficients Proof: $\sum_{k=0}^n {n \choose k} ^{2} = {2n \choose n}$.

Solution 1:

Combinatorial Proof

Consider the number of paths in the integer lattice from $(0,0)$ to $(n,n)$ using only single steps of the form: $$(i,j)→(i+1,j)$$ $$(i,j)→(i,j+1)$$

that is, either to the right or up. This process takes $2n$ steps, of which $n$ are steps to the right. Thus the total number of paths through the graph is equal to $\binom{2n}{n}$.

Now let us count the paths through the grid by first counting the paths:

$\qquad$ (1) from $(0,0)$ to $(k,n−k)$

and then the paths:

$\qquad$(2): from $(k,n−k)$ to $(n,n)$.

Note that each of these paths is of length $n$.

Since each path is $n$ steps long, every endpoint will be of the form $(k,n−k)$ for some $k\in\{1,2,\ldots,n\}$, representing $k$ steps right and $n−k$ steps up.

Note that the number of paths through $(k,n−k)$ is equal to $\binom{n}{k}$, since we are free to choose the $k$ steps right in any order. We can also count the number of n-step paths from the point $(k,n−k)$ to $(n,n)$. These paths will be composed of $n−k$ steps to the right and $k$ steps up. Therefore the number of these paths is equal to $\binom{n}{n−k}=\binom{n}{k}$.

Thus the total number of paths from $(0,0)$ to $(n,n)$ that pass through $(k,n−k)$ is equal to the product of the number of possible paths from $(0,0)$ to $(k,n−k)$ i.e. $\binom{n}{k}$, and the number of possible paths from $(k,n−k)$ to $(n,n)$ i.e $\binom{n}{k}$.

So the total number of paths through $(k,n−k)$ is equal to $\binom{n}{k}^2$.

Summing over all possible values of $k=0,\ldots,n$ gives the total number of paths.

Thus we get: $$ \sum_{k=0}^n\binom{n}{k}^2=\binom{2n}{n} $$

Solution 2:

Simpler to prove by induction is Vandermonde's Identity: $$ \sum_{j=0}^k\binom{n}{j}\binom{m}{k-j}=\binom{n+m}{k}\tag{1} $$ For $n=0$, note that the only non-zero term in the sum is when $j=0$. Therefore, the sum is $$ \binom{m}{k}\tag{2} $$ as $(1)$ says. Now, assume that $(1)$ holds for $n$, then compute $$ \begin{align} \sum_{j=0}^k\binom{n+1}{j}\binom{m}{k-j} &=\sum_{j=0}^k\binom{n}{j}\binom{m}{k-j}+\sum_{j=0}^k\binom{n}{j-1}\binom{m}{k-j}\\ &=\sum_{j=0}^k\binom{n}{j}\binom{m}{k-j}+\sum_{j=0}^{k-1}\binom{n}{j}\binom{m}{k-1-j}\\ &=\binom{n+m}{k}+\binom{n+m}{k-1}\\ &=\binom{n+m+1}{k}\tag{3} \end{align} $$ Thus, $(1)$ holds for $n+1$.

Applying $(1)$ to your question yields $$ \begin{align} \sum_{k=0}^n\binom{n}{k}^2 &=\sum_{k=0}^n\binom{n}{k}\binom{n}{n-k}\\ &=\binom{2n}{n}\tag{4} \end{align} $$

Solution 3:

Here is a proof by counting in two ways. Consider two urns, one with $n$ red balls and another containing $n$ blue balls. The total number of ways to choose $n$ balls (irrespective of color) in all from the two urns is ${2n \choose n}$. Alternatively, $k$ red balls can be chosen from the first urn (in ${n \choose k}$ ways) and for each such $k$-set, $n-k$ blues balls can then be picked from the other urn (in ${n \choose n-k}$ ways). Hence, the total number of ways to pick $n$ balls such that $k$ of them are red is ${n \choose k}{n \choose n-k} = {n \choose k}{n \choose k}$. Summing over $k$, the total number of ways is $\sum_{k=0}^{n}{n \choose k}^{2}$.