$\sum_{k=0}^n {n \choose k} ^{2} = {2n \choose n}$ - Generating function $\sum_{k=0}^\infty \binom nk x^k = (1+x)^n$. As part of a preparatory course in the contest PUTNAM, I have to show $\sum_{k=0}^n {n \choose k} ^{2} = {2n \choose n}$. I know that I can use the identity $\sum_{k=0}^n {n \choose k} {n \choose n-k}$ with the generating function $\sum_{k=0}^\infty \binom nk x^k = (1+x)^n$. 
However, I am not very aged (16 years), and generating functions are unknown to me. Someone would it be kind enough to describe me in detail how to do it?
 A: You don't have to use generating functions (unless that is what you want) to do this. This can be done by a simple counting idea. 
Suppose you have a group of $2n$ members where you have $n$ men and $n$ women. You are asked to find out the number of ways to pick $n$ people among this group and form a team. In how may ways can you do this? 
One way is to simple say it $\binom{2n}{n}$. Another way to do the same count is to consider a typical team which has $k$ men and $n-k$ women. In how many ways can you make such a team? This can be done in $\binom{n}{k}\binom{n}{n-k}$ ways. Now you sum this up with all possibilities for $k$. Thus
$$\sum_{k=1}^n \binom{n}{k}\binom{n}{n-k} = \binom{2n}{n}.$$
But $\binom{n}{k}=\binom{n}{n-k}.$ Therefore
$$\sum_{k=1}^n \binom{n}{k}^2= \binom{2n}{n}.$$
Using generating functions:
We start with $\sum_{k=0}^\infty \binom nk x^k = (1+x)^n$. 
Now consider the following:
\begin{align*}
(1+x)^n & = \sum_{k=0}^\infty \binom nk x^k\\
(1+x)^n(1+x)^n & = \left[\sum_{k=0}^\infty \binom nk x^k\right] \, \left[\sum_{k=0}^\infty \binom nk x^k\right]\\
(1+x)^{2n} & = \sum_{m=0}^{\infty} \left[\sum_{k=0}^{m}\binom{n}{k}\binom{n}{m-k}\right]x^{m}
\end{align*}
Now compute the coefficient of $x^{n}$ on both sides and compare.
A: You have, with the convention that $\binom{n}{k} = 0$ for $k > n$,
$$
(1+x)^n = \sum_{k=0}^\infty \binom{n}{k} x^k
$$
and
$$
(1+x)^{2n} = \sum_{k=0}^\infty \binom{2n}{k} x^k.
$$
But you also have
$$\begin{align}
(1+x)^{2n} &= (1+x)^n\cdot (1+x)^n = \left(\sum_{k=0}^\infty \binom{n}{k} x^k\right)\left(\sum_{k=0}^\infty \binom{n}{k} x^k\right) \\
&= \sum_{k=0}^\infty\sum_{\ell=0}^\infty \binom{n}{k}\binom{n}{\ell} x^kx^\ell 
= \sum_{k=0}^\infty\sum_{\ell=0}^\infty \binom{n}{k}\binom{n}{\ell} x^{k+\ell} \\
&= \sum_{k=0}^\infty\sum_{j=0}^k \binom{n}{k-j}\binom{n}{j} x^{k}
\end{align}$$
By unicity of the coefficients of the generating function,
$$
\sum_{k=0}^\infty \binom{2n}{k} x^k = \sum_{k=0}^\infty\sum_{j=0}^k \binom{n}{k-j}\binom{n}{j} x^{k}
$$
implies 
$$
\binom{2n}{k} = \sum_{j=0}^k \binom{n}{k-j}\binom{n}{j}
$$
for all $k$. In particular, for $k=n$,
$$
\binom{2n}{n} = \sum_{j=0}^n \binom{n}{n-j}\binom{n}{j} = \sum_{j=0}^n \binom{n}{j}^2.
$$
