$\sum_{k=0}^n {n \choose k} ^{2} = {2n \choose n}$ - Generating function $\sum_{k=0}^\infty \binom nk x^k = (1+x)^n$.

Question

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?

Answer 1

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

Answer 2

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.