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?
 A: 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.
A: 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. 
A: $\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}
A: 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.
$$
A: 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}$$
A: 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$$
