Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Discrete mathematics, continuous mathematics and probability (resit) / 2 / d / Solution

Fix $m\ge 0$, using the convention for binomial coefficients that $\left(\genfrac{}{}{0ex}{}{k}{m}\right)=0$ when $m>k$. At $n=0$, both $\left(\genfrac{}{}{0ex}{}{0}{m}\right)$ and $\left(\genfrac{}{}{0ex}{}{1}{m+1}\right)$ equal $1$ if $m=0$ and $0$ otherwise.

For the successor step, apply the induction hypothesis, then Pascal's rule:Thus mathematical induction proves the hockey-stick identityThe zero convention also covers the case $n<m$, without a separate starting index.