Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Discrete mathematics, continuous mathematics and probability / 2 / e / ii / Solution

For fixed $n\ge 0$, use mathematical induction on $k$. At $k=0$, both sides equal one. If the hockey-stick identity holds at $k$, then Pascal's identity givesThis is the required formula with $k$ replaced by $k+1$.