Toolkit 16

Hockey Stick Identity

\binom{k}{k}+\binom{k+1}{k}+\binom{k+2}{k}+\cdots+\binom{n}{k}=\binom{n+1}{k+1}

Proof

By Pascal's identity,

\binom{m+1}{k+1} = \binom{m}{k} + \binom{m}{k+1}.

Therefore,

\binom{m}{k} = \binom{m+1}{k+1} - \binom{m}{k+1}.

Writing this identity for $m = k, k+1, \ldots, n$ , we obtain

\binom{k}{k} = \binom{k+1}{k+1} - \binom{k}{k+1},

\binom{k+1}{k} = \binom{k+2}{k+1} - \binom{k+1}{k+1},

\vdots

\binom{n}{k} = \binom{n+1}{k+1} - \binom{n}{k+1}.

Adding these equations, all intermediate terms cancel. Since

\binom{k}{k+1} = 0,

we get

\binom{k}{k} + \binom{k+1}{k} + \cdots + \binom{n}{k} = \binom{n+1}{k+1}. \quad\square