= Solution
For <integers> $0\leq k\leq n$, define the <binomial coefficient> by
$$
\binom nk=\frac{n!}{k!(n-k)!},\qquad0!=1.
$$
Here 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\leq k<n$,
$$
\binom nk+\binom n{k+1}
=\frac{n!(k+1)+n!(n-k)}{(k+1)!(n-k)!}
=\frac{(n+1)!}{(k+1)!(n-k)!}
=\boxed{\binom{n+1}{k+1}}.
$$
This is <Pascal's identity>.
The required <hockey-stick identity> follows by <mathematical induction> on $m$, with $n\geq0$ fixed. For $m=0$, both sides are $1$. If it holds at $m$, adding the next <binomial coefficient> and using <Pascal's identity> gives
$$
\sum_{k=0}^{m+1}\binom{n+k}k
=\binom{n+m+1}m+\binom{n+m+1}{m+1}
=\binom{n+m+2}{m+1}.
$$
Therefore \b[for every $n,m\geq0$],
$$
\boxed{\sum_{k=0}^m\binom{n+k}k=\binom{n+m+1}m.}
$$
Back to article page
