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

$\newcommand{\+}{^{\dagger}} \newcommand{\angles}[1]{\left\langle #1 \right\rangle} \newcommand{\braces}[1]{\left\lbrace #1 \right\rbrace} \newcommand{\bracks}[1]{\left\lbrack #1 \right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil #1 \right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\down}{\downarrow} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\equalby}[1]{{#1 \atop {= \atop \vphantom{\huge A}}}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\isdiv}{\,\left.\right\vert\,} \newcommand{\ket}[1]{\left\vert #1\right\rangle} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left( #1 \right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ \begin{align} \color{#00f}{\large\sum_{k = 0}^{n}{n \choose k}^{2}}&= \sum_{k = 0}^{n}{n \choose k}\ \overbrace{\int_{\verts{z} = 1}{\pars{1 + z}^{n} \over z^{k + 1}} \,{\dd z \over 2\pi\ic}}^{\ds{n \choose k}}= \int_{\verts{z} = 1}{\pars{1 + z}^{n} \over z} \sum_{k = 0}^{n}{n \choose k}\pars{1 \over z}^{k}\,{\dd z \over 2\pi\ic} \\[3mm]&= \int_{\verts{z} = 1}{\pars{1 + z}^{n} \over z} \,\pars{1 + {1 \over z}}^{n}\,{\dd z \over 2\pi\ic} = \int_{\verts{z} = 1}{\pars{1 + z}^{2n} \over z^{n + 1}} \,{\dd z \over 2\pi\ic} =\color{#00f}{\large{2n \choose n}} \end{align}

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