= Solution
Define the <binomial coefficient> $\binom nk$ 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 $\binom nk=n!/[k!(n-k)!]$, with $\binom n0=\binom nn=1$.
Fix one distinguished element. The $k$-subsets not containing it are counted by $\binom{n-1}{k}$; 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>:
$$
\boxed{\binom{n-1}{k}+\binom{n-1}{k-1}=\binom nk.}
$$
For the summation, use <mathematical induction> on $k$, retaining an arbitrary fixed $n\ge0$. At $k=0$, both sides equal one. Suppose $\sum_{j=0}^k\binom{n+j}{j}=\binom{n+k+1}{k}$. Adding the next term and applying <Pascal's identity> gives
$$
\sum_{j=0}^{k+1}\binom{n+j}{j}=\binom{n+k+1}{k}+\binom{n+k+1}{k+1}=\binom{n+k+2}{k+1}.
$$
This is the required statement for $k+1$, completing the induction, including $n=0$. Hence the <hockey-stick identity> in this form is
$$
\boxed{\displaystyle\sum_{j=0}^k\binom{n+j}{j}=\binom{n+k+1}{k}\quad(n,k\ge0).}
$$
Back to article page
