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 , . Since for , the lower limit can also be taken as .
Key Formula
Where:
- = The fixed lower index of each binomial coefficient (the diagonal you travel along)
- = The upper index of the last term in the sum, with
- = The summation index, running from up to
How It Works
Proof by induction on . Base case : the left side is and the right side is . Inductive step: assume the identity holds for . Adding the next term gives by Pascal's rule, which is the identity for . Counting proof: to choose numbers from , sort by the largest number chosen. If it is , the other numbers come from , which gives ways. Adding over gives the left side.
Worked Example
Problem: Find the sum of the first 8 triangular numbers, , without adding them one by one.
Step 1: Rewrite each triangular number as a binomial coefficient. The th triangular number is . So the sum runs down the diagonal from to .
Step 2: Apply the Hockey Stick Theorem with and .
Step 3: Check by direct addition.
Answer: The sum of the first 8 triangular numbers is .
Why It Matters
In a discrete math or combinatorics course, this identity turns sums of polynomials into closed forms. For example, and . It also appears in analysis of nested loops in computer science, where a triple loop over runs 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 .
Correction: The formula assumes the sum starts at . If it starts at with , subtract the missing piece: . Here that gives .
