# Proof of a binomial identity $\sum_{k=0}^n {n \choose k}^{\!2} = {2n \choose n}.$

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

The exercise provides the following hint: $\,\,\displaystyle{n \choose k}={n\choose n-k}$.

Any help?

• Did you do some examples, say for $\;n=3,4,5,6...\;$ ? Did you try to use the rather huge hint? – DonAntonio Feb 25 '14 at 17:14
• I tried to think it in the way $\sum_{k=0}^n {n \choose k}^2 = \sum_{k=0}^n {n \choose k} {n \choose n-k}$ but didn't got very far... – FranckN Feb 25 '14 at 17:16
• Think of a combinatorial argument: in how many ways can you pick $n$ out of $2n$ objects? – Hoda Feb 25 '14 at 17:17
• $(x+1)^{m+n}=(x+1)^m(x+1)^n$ – Lucian Feb 25 '14 at 17:20
• – Martin Sleziak Dec 11 '16 at 7:31

Following the hint given by the OP, it suffices to show that $$\sum_{k=0}^n {n \choose k}^{\!2}=\sum_{k=0}^n {n \choose k}{n \choose {n-k}} = {2n \choose n}.$$ The last equality is a consequence of the following more general identity (known as Vandermonde's identity) $$\sum_{j=0}^k \binom{n-m}{k-j}\binom{m}{j}=\binom{n}{k},$$ where $n\ge m,k\ge 0$, which in turn is just an equality of the coefficients of $x^k$ is the left and right hand side of the binomial expansions of $$(1+x)^{n-m}(1+x)^m=(1+x)^n.$$

Think of it this way.

On the right side, you're choosing $n$ objects from $2n$ objects.

On the left side, it's equal to $\sum\binom{n}{k}\binom{n}{n-k}$. So, divide the $2n$ objects into 2 groups, both of $n$ size. Then, the total number of way of choosing $n$ objects is partitioning over how many elements you choose from one group, and the remaining $n-k$ elements from the other group.

If we don't use the hint, we can consider the left side as still partitioning over picking $k$ objects from the first group, and then selecting $k$ elements not to choose from the second group, which would be $n-k$ elements you're choosing, so you still get $k$ elements in total.


If we choose $k$ elements from a set with $n$ elements this is similar to don't choose $n-k$ elements from this set hence the number of subset with $k$ elements is equal to the number of subset with $n-k$ elements and this explain the given hint $${n\choose k}={n\choose n-k}$$

Now if we have two sets each one with $n$ elements and we choose $n$ elements: $k$ elements from the first and $n-k$ from the second set then the number of choice is $$\sum_{k=0}^n{n\choose k}{n\choose n-k}=\sum_{k=0}^n{n\choose k}{n\choose k}={2n\choose n}$$

Another way: Count the number of paths of length $2n$ on the integers taking $0$ to itself. Since there need to be $n$ lefts and $n$ rights, the total number is ${\displaystyle {2n \choose n}}$. The number of paths where the first $n$ moves contains $k$ rights and the second $n$ moves contains $n-k$ rights is ${\displaystyle {n \choose k}{n \choose n - k} = {n \choose k}^2}$. Adding this over all $k$ gives the identity.

Here is another way of doing it you just have to look at the binomial expansion of $(1+x)^n(1+\frac{1}{x})^n$ carefully:

$(1+x)^n(1+\frac{1}{x})^n = (^nC_0 + ^nC_1x + ^nC_2x^2 \cdots)(^nC_0 + ^nC_1\frac{1}{x} + ^nC_2\frac{1}{x^2} \cdots)$

you will find that $\sum_{k=0}^{n} (^nC_k)^2$ is actually the coefficient of $x^0$.

$$(1+x)^n(1+\frac{1}{x})^n = (1+x)^{2n}\frac{1}{x^n}$$ So the coefficient of $x^0$ in the expansion is $^{2n}C_n$, which proves the identity: $$\sum_{k=0}^{n} (^nC_k)^2 = ^{2n}C_n$$