= Solution
For nonnegative <integers> $n,m$, prove the <hockey-stick identity> by <mathematical induction> on $m$. The <induction base case> $m=0$ is $\binom n0=\binom{n+1}0=1$. If the formula holds through $m-1$, <Pascal's identity> gives
$$
\sum_{j=0}^m\binom{n+j}j
=\binom{n+m}{m-1}+\binom{n+m}m
=\binom{n+m+1}m.
$$
This supplies the <inductive step>.
A <binary string> containing exactly $n$ zeroes and $j$ ones has length $n+j$. Choosing its $j$ one-positions gives $\binom{n+j}j$ possibilities. Different values of $j$ give disjoint collections, so <counting binary strings with bounded ones> yields
$$
\boxed{\sum_{j=0}^m\binom{n+j}j=\binom{n+m+1}m.}
$$
This includes $n=0$: the $m+1$ strings are the empty string and the all-one strings of lengths one through $m$.
Back to article page
