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

Solution 1:

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

Solution 2:

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.

Solution 3:

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

Solution 4:

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

Solution 5:

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.