A student verifies the hockey stick identity C(2,2) + C(3,2) + C(4,2) = C(5,3) by computing 1 + 3 + 6 = 10 = C(5,3) and declares the identity proved. What is the limitation of this approach?
AThe arithmetic is wrong — 1 + 3 + 6 does not equal 10
BNumerical verification confirms a specific instance but does not explain why the identity must hold for all valid n and r
CThis method cannot be extended to r = 2 for larger n
DThe student should trace the hockey stick shape in Pascal's triangle instead of computing directly
Checking one case confirms the identity holds there, but mathematics requires a proof that works for all n and r. The double-counting proof answers 'why' by showing both sides count the same set of objects — a level of explanation numerical verification cannot provide.
Question 2 Multiple Choice
In the double-counting proof of the hockey stick identity, why is conditioning on the largest element chosen the key move?
ATo reduce the problem to a smaller instance using strong induction on n
BBecause the largest element uniquely determines the rest of the subset
CBecause fixing which element is the maximum transforms the remaining choice into a specific binomial coefficient, and summing over all possible maxima produces exactly the hockey stick sum
DTo ensure all chosen elements form a consecutive sequence in the original set
Once you fix that the largest chosen element is r+k+1, the remaining r elements must be drawn from the k+r elements below it, giving C(r+k, r). Summing k from 0 to n−r yields the hockey stick. The elegance is that a combinatorial question about the maximum element decomposes the problem into exactly the terms on the left side of the identity.
Question 3 True / False
The Hockey Stick Identity is an example of the double-counting technique: the same combinatorial quantity is counted in two different ways, and equating those counts yields the identity.
TTrue
FFalse
Answer: True
This is precisely how the canonical proof works. C(n+1, r+1) counts subsets of size r+1 from {1,...,n+1}. Conditioning on the maximum element and summing gives the hockey stick sum. Since both expressions count the same thing, they are equal — revealing not just that the identity is true but why.
Question 4 True / False
The 'hockey stick' name refers to the curved shape of the algebraic formula when written in standard sigma notation.
TTrue
FFalse
Answer: False
The name comes from the visual shape traced in Pascal's triangle: the summed binomial coefficients form a straight diagonal shaft, and the result appears just below and to one side of the final term, like the curved blade of a hockey stick. The name is geometric, not algebraic.
Question 5 Short Answer
Explain in your own words why conditioning on the largest element in the double-counting proof produces the hockey-stick sum and not some other formula.
Think about your answer, then reveal below.
Model answer: Fixing the maximum element to be value m reduces the choice of remaining r elements to the m−1 elements below it, yielding C(m−1, r). Summing over all possible values of m from r+1 to n+1 generates exactly the terms in the hockey stick sum, and these are exhaustive and mutually exclusive cases that together cover all (r+1)-element subsets.
The partition by maximum element is key: every (r+1)-element subset has a unique maximum, so the cases are disjoint and exhaustive. This is what guarantees the sum counts exactly C(n+1, r+1) without overlap or omission — the identity falls out as a consequence of how the partition is structured.