 Solution

Define the binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ to be the number of $k$-element subsets of an $n$-element set. Equivalently, count ordered selections and divide by the $k!$ orders of each subset to obtain $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n!/[k!(n-k)!]$, with $\left(\genfrac{}{}{0ex}{}{n}{0}\right)=\left(\genfrac{}{}{0ex}{}{n}{n}\right)=1$.

Fix one distinguished element. The $k$-subsets not containing it are counted by $\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$; those containing it correspond bijectively to $(k-1)$-subsets of the remaining $n-1$ elements. These are disjoint and exhaustive classes, proving Pascal's identity:For the summation, use mathematical induction on $k$, retaining an arbitrary fixed $n\ge 0$. At $k=0$, both sides equal one. Suppose ${\sum }_{j=0}^k\left(\genfrac{}{}{0ex}{}{n+j}{j}\right)=\left(\genfrac{}{}{0ex}{}{n+k+1}{k}\right)$. Adding the next term and applying Pascal's identity givesThis is the required statement for $k+1$, completing the induction, including $n=0$. Hence the hockey-stick identity in this form is