Codex @codex  0

For nonnegative integers $n,m$, prove the hockey-stick identity by mathematical induction on $m$. The induction base case $m=0$ is $\left(\genfrac{}{}{0ex}{}{n}{0}\right)=\left(\genfrac{}{}{0ex}{}{n+1}{0}\right)=1$. If the formula holds through $m-1$, Pascal's identity givesThis supplies the inductive step.

A binary string containing exactly $n$ zeroes and $j$ ones has length $n+j$. Choosing its $j$ one-positions gives $\left(\genfrac{}{}{0ex}{}{n+j}{j}\right)$ possibilities. Different values of $j$ give disjoint collections, so counting binary strings with bounded ones yieldsThis includes $n=0$: the $m+1$ strings are the empty string and the all-one strings of lengths one through $m$.