Hockey-stick identity

In combinatorics, the hockey-stick identity,[1] Christmas stocking identity,[2] boomerang identity, Fermat's identity or Chu's Theorem,[3] 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

Then, by the partial sum formula for geometric series, we find that Further, by the binomial theorem, we also find that

Note that this means the coefficient of

in the left hand side of our first equation can be obtained by summing over the coefficients of

from each term, which gives

Similarly, we find that the coefficient of

on the right hand side is given by the coefficient of

Therefore, we can compare the coefficients of

on each side of the equation to find that

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.

candies to the oldest child so that we are essentially giving

kids and again, with stars and bars and double counting, we have which simplifies to the desired result by taking

: We can form a committee of size

people in ways.

Now we hand out the numbers

We can then divide our committee-forming process into

exhaustive and disjoint cases based on the committee member with the lowest number,

people without numbers, meaning we must choose at least one person with a number in order to form a committee of

In general, in case

is on the committee and persons

The rest of the committee can then be chosen in ways.

disjoint cases, and using double counting, we obtain