Binomial

Well done Ang Zhi Ping from River Valley High School, Singapore for your excellent solution to this question.

Let the binomial coefficient $n!/r!(n-r)!$ be denoted by $$\begin{equation}{n\choose r}.\end{equation}$$

By considering powers of $(1 + x)$ show that $$\sum_{k=0}^n {n\choose k}^2 = {2n \choose n}$$

As $(1 + x)^n(1 + x)^n = (1 + x)^{2n} \quad (1)$, we write down the Binomial expansion giving: $$\begin{equation*}\left[\sum_{p=0}^n {n\choose p} x^p\right]\left[\sum_{q=0}^n {n\choose q} x^q\right] = \sum_{r=0}^{2n} {2n\choose r}x^r. \end{equation*}$$ The left hand side of the equation is $$\begin{equation*}\left[{n\choose 0} + {n\choose 1}x + \cdots + {n\choose n}x^n\right] \left[{n\choose 0} + {n\choose 1}x + \cdots + {n\choose n}x^n\right].\end{equation*}$$ So the coefficient of $x^n$ on the left hand side of (1) is $$\begin{equation*}{n\choose 0}{n\choose n} + {n\choose 1}{n\choose n-1} + {n\choose 2}{n\choose n-2} + \cdots +{n\choose n-1}{n\choose 1} + {n\choose n}{n\choose 0}.\end{equation*}$$ Since $$\begin{equation}{n\choose r} = {n\choose n-r}\end{equation}$$ we see that the coefficient of $x^n$ on the left hand side of (1) is $$\begin{equation}\sum_{k=0}^n {n\choose k}^2.\end{equation}$$ As the coefficient of $x^n$ on the right hand side of (1) is $$\begin{equation}{2n\choose n}\end{equation}$$ the given formula is proven.