# 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$. Commented Sep 16, 2015 at 18:12
• Then would you able to answer the question : math.stackexchange.com/questions/1473827/… ?
– user230283
Commented Oct 10, 2015 at 21:21
• Does this answer your question? Combinatorial proof of summation of $\sum\limits_{k = 0}^n {n \choose k}^2= {2n \choose n}$ Commented May 1, 2020 at 10:52

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

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}

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

Proof using binomial theorem:

By the binomial theorem we have $$(1+x)^{2n}=\sum_{k=0}^{2n}\binom{2n}{k}x^k\tag{1}$$ Also, $$(1+x)^{2n}=(1+x)^n(1+x)^n=\left(\sum_{j=0}^{n}\binom{n}{k}x^j\right)\left(\sum_{l=0}^{n}\binom{n}{l}x^l\right)\tag{2}$$

Let us look at the coefficient for the term $$x^n$$. From $$(1)$$ this is $$\binom{2n}{n}$$, from $$(2)$$ we need to sum the coefficients for $$x^{j+l}$$ with $$j+l=n$$. This looks like $$\sum_{k+l=n}\binom{n}{k}\binom{n}{l}=\sum_{k=0}^{n}\binom{n}{k}\binom{n}{n-k}=\sum_{k=0}^{n}\binom{n}{k}^2$$ Therefore $$\boxed{\binom{2n}{n}=\sum_{k=0}^{n}\binom{n}{k}^2}$$

I prove this using a committee forming argument:

Our argument is that this expression is finding the amount of ways to choose $$n$$ total people from two groups of $$n$$ people. First, let's rewrite this expression. We first note that$$\binom{n}{0}^2 + \binom{n}{1}^2 + \cdots + \binom{n}{n}^2$$can be rewritten as$$\binom n0\times \binom nn+\binom n1\times \binom n{n-1}+\cdots+\binom nn\times \binom n0$$because $$\binom nk = \binom n{n-k}$$. Now, let's see what this means. We can imagine two groups of $$n$$ people. $$\binom n0 \cdot \binom nn$$ tells us that we choose $$n$$ people from the two groups of $$n$$ because $$0+n=n$$. Similarly, we have $$\binom n1+\binom n{n-1}$$ is also choosing $$n$$ people from the two groups of $$n$$ (since $$1+n-1 = n$$). Clearly, all we're doing here is finding the amount of ways to choose $$n$$ people from two groups of $$n$$ people, which is our argument. This can be done in $$\binom{2n}{n}$$ ways. Therefore,$$\binom{n}{0}^2 + \binom{n}{1}^2 + \cdots + \binom{n}{n}^2 = \binom{2n}{n},$$ or simply just $$\sum_{k=0}^{n}\binom nk ^2=\binom{2n}{n}.$$