Past exam of the mathematics course of the University of Cambridge / 2014 / ia / Paper 4 / 2E / Solution

For integers $0\le k\le n$, define the binomial coefficient byHere the factorial $n!$ is the product of the positive integers up to $n$. This also counts the $k$-element subsets of an $n$-element set: an ordered choice has $n!/(n-k)!$ possibilities, and each subset is ordered in $k!$ ways.

Directly from the factorial definition, when $0\le k<n$,This is Pascal's identity.

The required hockey-stick identity follows by mathematical induction on $m$, with $n\ge 0$ fixed. For $m=0$, both sides are $1$. If it holds at $m$, adding the next binomial coefficient and using Pascal's identity givesTherefore for every $n,m\ge 0$,