Binomial
By considering powers of (1+x), show that the sum of the squares of
the binomial coefficients from 0 to n is 2nCn
Age
16 to 18
Challenge level
Problem
Show that
\[\sum_{k=0}^n {n\choose k}^2 \equiv {2n \choose n}.\]
Getting Started
Consider powers of $1 + x$.
If you can't get started investigate the formula for $n = 2, 3,4 ...$
Student Solutions
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.
Teachers' Resources
Why do this problem?
The problem gives practice in using the notation for Binomial coefficients and manipulating algebraic expressions. In problem solving mode, if they can't get started, they might first try to work on the formula for small integer values of $n$.
Possible approach
Use as a revision exercise.
Key questions
If ${2n \choose n}$ is a binomial coefficient in the expansion of some power of $(1 + x)$ what can you say about the expansion and about the term where it occurs?
What do we know about ${n\choose r}$ and ${n\choose n-r}$?
Possible support
Ask learners to find the coefficient of $x^2$ in the expansion
of $(1+x)^4$, the coefficient of $x^3$ in the expansion of $(1
+x)^6$ and then the coefficient of $x^4$ in the expansion of $(1 +
x)^8$ and then ask them to try to connect their results to the
problem given.
It might help to do the problem
Summit first.
You could ask students to show that the sum of the $n$th row in Pascal's Triangle is $2^n$ first - so that they have a sense of achievement even if they don't succeed in proving the result in this problem.