MathGoldMedalist
Sign InRegister
Back to Toolkit

Toolkit 16

Hockey Stick Identity

(kk)+(k+1k)+(k+2k)+⋯+(nk)=(n+1k+1)\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,

(m+1k+1)=(mk)+(mk+1).\binom{m+1}{k+1} = \binom{m}{k} + \binom{m}{k+1}.

Therefore,

(mk)=(m+1k+1)−(mk+1).\binom{m}{k} = \binom{m+1}{k+1} - \binom{m}{k+1}.

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

(kk)=(k+1k+1)−(kk+1),\binom{k}{k} = \binom{k+1}{k+1} - \binom{k}{k+1},
(k+1k)=(k+2k+1)−(k+1k+1),\binom{k+1}{k} = \binom{k+2}{k+1} - \binom{k+1}{k+1},
⋮\vdots
(nk)=(n+1k+1)−(nk+1).\binom{n}{k} = \binom{n+1}{k+1} - \binom{n}{k+1}.

Adding these equations, all intermediate terms cancel. Since

(kk+1)=0,\binom{k}{k+1} = 0,

we get

(kk)+(k+1k)+⋯+(nk)=(n+1k+1).□\binom{k}{k} + \binom{k+1}{k} + \cdots + \binom{n}{k} = \binom{n+1}{k+1}. \quad\square