= Solution
Define the <binomial coefficient> $\binom nk$ 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 $\binom n0=1$.
Distinguish one element of the set. A $k$-element subset either omits it, giving $\binom{n-1}k$ possibilities, or contains it and chooses its other $k-1$ elements from the remaining set, giving $\binom{n-1}{k-1}$ possibilities. These cases are disjoint and exhaustive, proving <Pascal's identity>:
$$
\boxed{\binom{n-1}k+\binom{n-1}{k-1}=\binom nk.}
$$
For the requested sum, fix $n\ge0$ and use <mathematical induction> on $k$. At $k=0$, both sides equal one. If the assertion holds at $k$, adding the next summand 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},
$$
where the last equality is <Pascal's identity>. Thus the induction proves the <hockey-stick identity> for all nonnegative $n,k$:
$$
\boxed{\sum_{j=0}^k\binom{n+j}j=\binom{n+k+1}k.}
$$
Back to article page
