For faster navigation, this Iframe is preloading the Wikiwand page for
Hockey-stick identity.
Hockey-stick identity
Recurrence relations of binomial coefficients in Pascal's triangle
In combinatorial mathematics, 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).
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 then divide our committee-forming process into exhaustive and disjoint cases based on the committee member with the lowest number, . Note that there are only people without numbers, meaning we must choose at least one person with a number in order to form a committee of people. In general, in case , person is on the committee and persons are not on the committee. The rest of the committee can then be chosen in
ways. Now we can sum the values of these disjoint cases, and using double counting, we obtain
This browser is not supported by Wikiwand :( Wikiwand requires a browser with modern capabilities in order to provide you with the best reading experience. Please download and use one of the following browsers:
Your input will affect cover photo selection, along with input from other users.
X
Get ready for Wikiwand 2.0 🎉! the new version arrives on September 1st! Don't want to wait?
Oh no, there's been an error
Please help us solve this error by emailing us at support@wikiwand.com
Let us know what you've done that caused this error, what browser you're using, and whether you have any special extensions/add-ons installed.
Thank you!