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

Prove that $\sum_{k=0}^n {n \choose k} ^{2} = {2n \choose n}$.

I am trying to prove this by induction. I am having some difficulty after the induction step.

Here is what I have so far:

I start with ${2(m+1) \choose m+1}$ and want to work my way to the summation, with m+1.

Using Pascal's law twice, ${2(m+1) \choose m+1}$= ${2m \choose m-1}$+${2m \choose m}$+${2m \choose m}$+${2m \choose m+1}$= $\sum_{k=0}^m {m \choose k} ^{2}$ +$\sum_{k=0}^m {m \choose k} ^{2}$+${2m \choose m+1}$+${2m \choose m+1}$= 2[$\sum_{k=0}^m {m \choose k} ^{2}$+${2m \choose m+1}]$.

The second equality is by the induction hypothesis. I am not sure what to do about the extra factor of two and if there are any theorems about binomial coefficients that could help.

Thank you!

• Probably irrelevant, since you want a proof by induction, but: the equivalent identity $\sum_{k=0}^n \binom nk \binom n{n-k} = \binom{2n}n$ is a convolution identity, which turns out to be easy to prove using the generating function $\sum_{k=0}^\infty \binom nk x^k = (1+x)^n$. – Greg Martin Sep 16 '15 at 18:12
• Then would you able to answer the question : math.stackexchange.com/questions/1473827/… ? – user230283 Oct 10 '15 at 21:21

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}

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

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

Let's see what happens if we consider \begin{align*} \binom{n+1}{k}^{\!2} &= \left(\binom{n}{k-1} + \binom{n}{k}\right)^{\!2} \\ &= \binom{n}{k-1}^{\!2} + \binom{n}{k}^{\!2} + 2\binom{n}{k-1}\binom{n}{k}. \end{align*} Now taking the sum from $k = 0$ to $n+1$, observing that $\binom{n}{n+1} = 0$ and $\binom{n}{-1} = 0$, we get $$\sum_{k=0}^{n+1} \binom{n+1}{k}^{\!2} = 2\sum_{k=0}^n \binom{n}{k}^{\!2} + 2\sum_{k=1}^{n} \binom{n}{k-1}\binom{n}{k}.$$ We now wish to show the second sum on the RHS is $\binom{2n}{n+1}$. But this is a special case of Vandermonde's convolution/identity $$\sum_x \binom{r}{a+x}\binom{s}{b-x} = \binom{r+s}{a+b}, \quad a, b \in \mathbb Z,$$ where $r = s = b = 1$ and $a = -1$. The rest follows by induction from the calculations you previously established.

But here's the funny thing: the original identity is itself a special case of Vandermonde's, with the choice $r = s = n$, $x = k$, $a = 0$, $b = n$, since $\binom{n}{n-k} = \binom{n}{k}$. Here's another approach: Inductive Proof for Vandermonde's Identity?

I know you want an induction proof to this but I can't resist giving you a combinatorial one. The right side is the answer to the question: "In how many ways can I draw $n$ element from a $2n$ element set" - it's obviously ${2n\choose n}$

To get the right side lets divide our $2n$ set into two n-element subsets, and lets draw $k$ elements from the first one and $n-k$ elements from the second one. There are ${n\choose k}{n\choose n-k}={n\choose k}{n\choose k}={n\choose k}^2$ ways to do it. We can do it for every k from 1 up to n and the sum gives us the total numer of ways to choose n elements from a 2n set, therefore: $$\sum_{k=0}^n {n \choose k} ^{2} = {2n \choose n}$$