Hockey-stick identity

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

Pascal's triangle, rows 0 through 7. The hockey stick identity confirms, for example: for n=5, r=2: 1+3+6+10=20; for n=6, r=3: 1+4+10+20=35.

In combinatorial mathematics, the identity

is known as the hockey-stick[1] or Christmas stocking identity.[2] That 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.

Proofs[edit]

The inductive and algebraic proofs both make use of Pascal's identity:

Inductive proof[edit]

This identity can be proven by induction on .

Base case Let ;

Inductive step Suppose, for some ,

Then

Algebraic proof[edit]

We use a telescoping argument to simplify the computation of the sum:

A combinatorial proof[edit]

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 :

Another combinatorial proof[edit]

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. Now we can sum the values of these disjoint cases, getting

See also[edit]

References[edit]

  1. ^ CH Jones (1996) Generalized Hockey Stick Identities and N-Dimensional Block Walking. Fibonacci Quarterly 34(3), 280-288.
  2. ^ W., Weisstein, Eric. "Christmas Stocking Theorem". mathworld.wolfram.com. Retrieved 2016-11-01.

External links[edit]