Mathwords logoMathwords

Hockey Stick Theorem — Definition, Formula & Example

The Hockey Stick Theorem is a shortcut for adding binomial coefficients that run down a diagonal of Pascal's triangle. The total equals the single entry diagonally below the last term. Drawn on the triangle, the diagonal and that last entry form the shape of a hockey stick.

For integers n≥r≥0n \ge r \ge 0, ∑i=rn(ir)=(n+1r+1)\sum_{i=r}^{n} \binom{i}{r} = \binom{n+1}{r+1}. Since (ir)=0\binom{i}{r} = 0 for 0≤i<r0 \le i < r, the lower limit can also be taken as i=0i = 0.

Key Formula

∑i=rn(ir)=(rr)+(r+1r)+⋯+(nr)=(n+1r+1)\sum_{i=r}^{n} \binom{i}{r} = \binom{r}{r} + \binom{r+1}{r} + \cdots + \binom{n}{r} = \binom{n+1}{r+1}
Where:
  • rr = The fixed lower index of each binomial coefficient (the diagonal you travel along)
  • nn = The upper index of the last term in the sum, with n≥rn \ge r
  • ii = The summation index, running from rr up to nn

How It Works

Proof by induction on nn. Base case n=rn = r: the left side is (rr)=1\binom{r}{r} = 1 and the right side is (r+1r+1)=1\binom{r+1}{r+1} = 1. Inductive step: assume the identity holds for nn. Adding the next term gives (n+1r+1)+(n+1r)=(n+2r+1)\binom{n+1}{r+1} + \binom{n+1}{r} = \binom{n+2}{r+1} by Pascal's rule, which is the identity for n+1n+1. Counting proof: to choose r+1r+1 numbers from {1,…,n+1}\{1, \dots, n+1\}, sort by the largest number chosen. If it is i+1i+1, the other rr numbers come from {1,…,i}\{1, \dots, i\}, which gives (ir)\binom{i}{r} ways. Adding over i=r,…,ni = r, \dots, n gives the left side.

Worked Example

Problem: Find the sum of the first 8 triangular numbers, 1+3+6+10+15+21+28+361 + 3 + 6 + 10 + 15 + 21 + 28 + 36, without adding them one by one.
Step 1: Rewrite each triangular number as a binomial coefficient. The kkth triangular number is Tk=k(k+1)2=(k+12)T_k = \frac{k(k+1)}{2} = \binom{k+1}{2}. So the sum runs down the r=2r = 2 diagonal from (22)\binom{2}{2} to (92)\binom{9}{2}.
∑k=18Tk=∑i=29(i2)\sum_{k=1}^{8} T_k = \sum_{i=2}^{9} \binom{i}{2}
Step 2: Apply the Hockey Stick Theorem with r=2r = 2 and n=9n = 9.
∑i=29(i2)=(103)=10⋅9⋅83⋅2⋅1=120\sum_{i=2}^{9} \binom{i}{2} = \binom{10}{3} = \frac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = 120
Step 3: Check by direct addition.
1+3+6+10+15+21+28+36=1201 + 3 + 6 + 10 + 15 + 21 + 28 + 36 = 120
Answer: The sum of the first 8 triangular numbers is (103)=120\binom{10}{3} = 120.

Why It Matters

In a discrete math or combinatorics course, this identity turns sums of polynomials into closed forms. For example, ∑k=1nk=(n+12)\sum_{k=1}^{n} k = \binom{n+1}{2} and ∑k=1nk(k+1)/2=(n+23)\sum_{k=1}^{n} k(k+1)/2 = \binom{n+2}{3}. It also appears in analysis of nested loops in computer science, where a triple loop over 1≤i<j<k≤n1 \le i < j < k \le n runs (n3)\binom{n}{3} times.

Common Mistakes

Mistake: Applying the formula directly when the sum starts partway down the diagonal instead of at its top. For example, a student writes (52)+⋯+(92)=(103)\binom{5}{2} + \cdots + \binom{9}{2} = \binom{10}{3}.
Correction: The formula assumes the sum starts at (rr)\binom{r}{r}. If it starts at (mr)\binom{m}{r} with m>rm > r, subtract the missing piece: ∑i=mn(ir)=(n+1r+1)−(mr+1)\sum_{i=m}^{n} \binom{i}{r} = \binom{n+1}{r+1} - \binom{m}{r+1}. Here that gives 120−10=110120 - 10 = 110.

Related Terms

  • Theorem — The kind of proven statement this result is
  • Binomial Theorem — Expansion formula whose coefficients fill Pascal's triangle
  • Combinatorics — Field of counting where this identity is a standard tool
  • Multinomial Coefficient — Generalizes the binomial coefficients summed in this identity
  • Twelvefold Way — Classifies twelve basic counting problems, several answered by binomial coefficients
  • Pascal's Triangle — Triangle of binomial coefficients where the diagonal sums occur