 Solution

Define the binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ as the number of $k$-element subsets of an $n$-element set. Equivalently it is $n!/[k!(n-k)!]$: there are $n(n-1)\cdots (n-k+1)$ ordered lists of $k$ distinct elements, and each subset gives $k!$ such lists. The empty subset gives $\left(\genfrac{}{}{0ex}{}{n}{0}\right)=1$.

Distinguish one element of the set. A $k$-element subset either omits it, giving $\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$ possibilities, or contains it and chooses its other $k-1$ elements from the remaining set, giving $\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$ possibilities. These cases are disjoint and exhaustive, proving Pascal's identity:For the requested sum, fix $n\ge 0$ and use mathematical induction on $k$. At $k=0$, both sides equal one. If the assertion holds at $k$, adding the next summand giveswhere the last equality is Pascal's identity. Thus the induction proves the hockey-stick identity for all nonnegative $n,k$: