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

Question

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!

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

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

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

Answer 4

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?

Answer 5

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

Answer 6

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

Answer 7

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