# 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!

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