Maths WorkshopMaths problems with full solutions
Exercise 805Combinatorics › Binomial coefficientsL1Added 3 Nov 2026

The hockey-stick identity

#hockey stick#sum identity#Pascal

Statement

Prove that ∑k=rn(kr)=(n+1r+1)\sum_{k=r}^{n}\binom{k}{r}=\binom{n+1}{r+1}.

Hint

Use Pascal's identity or induction on nn.

Show solutionHide solution

Solution

Induction on nn. Base n=rn=r: (rr)=(r+1r+1)=1\binom{r}{r}=\binom{r+1}{r+1}=1.

Step. Suppose ∑k=rn(kr)=(n+1r+1)\sum_{k=r}^{n}\binom{k}{r}=\binom{n+1}{r+1}. Then
∑k=rn+1(kr)=(n+1r+1)+(n+1r)=(n+2r+1)\sum_{k=r}^{n+1}\binom{k}{r}=\binom{n+1}{r+1}+\binom{n+1}{r}=\binom{n+2}{r+1}
by Pascal.

Conclusion. The identity holds.

Name. Plotted on Pascal's triangle, the sum follows a hockey stick shape.