Hockey-stick identity

In combinatorial mathematics, the hockey-stick identity, Christmas stocking identity, boomerang identity, Fermat's identity or Chu's Theorem, states that if are integers, then The name stems from the graphical representation of the identity on Pascal's triangle: when the addends represented in the summation and the sum itself are highlighted, the shape revealed is vaguely reminiscent of those objects (see hockey stick, Christmas stocking). Using sigma notation, the identity states or equivalently, the mirror-image by the substitution : We have Let , and compare coefficients of . The inductive and algebraic proofs both make use of Pascal's identity: This identity can be proven by mathematical induction on . Base case Let ; Inductive step Suppose, for some , Then We use a telescoping argument to simplify the computation of the sum: Imagine that we are distributing indistinguishable candies to distinguishable children. By a direct application of the stars and bars method, there are ways to do this. Alternatively, we can first give candies to the oldest child so that we are essentially giving candies to kids and again, with stars and bars and double counting, we have which simplifies to the desired result by taking and , and noticing that : We can form a committee of size from a group of people in ways. Now we hand out the numbers to of the people. We can divide this into disjoint cases. In general, in case , , person is on the committee and persons are not on the committee. This can be done in ways.