Past exam of the mathematics course of the University of Cambridge / 2011 / ia / Paper 4 / 7E (Numbers and Sets)

Define the binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{i}\right)$ to be the number of $i$-element subsets of an $n$-element set. Counting ordered selections and dividing by the $i!$ orders of each subset givesEvery subset has exactly one size, while each of the $n$ elements can independently be included or omitted. Hence the power set has $2^n$ members andTo prove the binomial theorem, expand the product of $n$ factors $(1+x)$. A term $x^i$ results from choosing $x$ from precisely an $i$-element subset of the factors and choosing one elsewhere. Its coefficient is therefore $\left(\genfrac{}{}{0ex}{}{n}{i}\right)$. This is a finite distributive expansion, valid for every real $x$, and givesDifferentiate this polynomial identity and set $x=1$:A second derivative gives $\sum i(i-1)\left(\genfrac{}{}{0ex}{}{n}{i}\right)=n(n-1)2^{n-2}$ for $n\ge 2$. Since $i^2=i(i-1)+i$, it follows thatThe formula also holds for $n=1$, when its value is one; that case can be checked directly without differentiating twice.

For the squared binomial coefficients, compare the coefficient of $x^n$ in $(1+x{)}^n(1+x{)}^n=(1+x{)}^{2n}$. On the left it is ${\sum }_i\left(\genfrac{}{}{0ex}{}{n}{i}\right)\left(\genfrac{}{}{0ex}{}{n}{n-i}\right)$, and the binomial coefficient symmetry gives $\left(\genfrac{}{}{0ex}{}{n}{n-i}\right)=\left(\genfrac{}{}{0ex}{}{n}{i}\right)$. ThusFinally put $S={\sum }_{i}i{\left(\genfrac{}{}{0ex}{}{n}{i}\right)}^2$ and replace the index $i$ by $n-i$. The same symmetry gives $S={\sum }_i(n-i){\left(\genfrac{}{}{0ex}{}{n}{i}\right)}^2$. Adding the two expressions and using the preceding identity yields