To install click the Add extension button. That's it.

The source code for the WIKI 2 extension is being checked by specialists of the Mozilla Foundation, Google, and Apple. You could also do it yourself at any point in time.

4,5
Kelly Slayton
Congratulations on this excellent venture… what a great idea!
Alexander Grigorievskiy
I use WIKI 2 every day and almost forgot how the original Wikipedia looks like.
Live Statistics
English Articles
Improved in 24 Hours
Added in 24 Hours
Languages
Recent
Show all languages
What we do. Every page goes through several hundred of perfecting techniques; in live mode. Quite the same Wikipedia. Just better.
.
Leo
Newton
Brights
Milds

Hockey-stick identity

From Wikipedia, the free encyclopedia

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

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).

YouTube Encyclopedic

  • 1/5
    Views:
    4 978
    5 668
    25 091
    66 960
    35 837
  • Art of Problem Solving: Hockey Stick Identity Part 2
  • Art of Problem Solving: Hockey Stick Identity Part 5
  • Art of Problem Solving: Pascal's Identity
  • Art of Problem Solving: Introducing Pascal's Triangle
  • Art of Problem Solving: Counting Paths on a Grid

Transcription

Formulations

Using sigma notation, the identity states

or equivalently, the mirror-image by the substitution :

Proofs

Generating function proof

Let . 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 is given by .

Thus, 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 in , which is

Therefore, we can compare the coefficients of on each side of the equation to find that

Inductive and algebraic proofs

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

Inductive proof

This identity can be proven by mathematical induction on .

Base case Let ;

Inductive step Suppose, for some ,

Then

Algebraic proof

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

Combinatorial proofs

Proof 1

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 :

Proof 2

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


See also


References

  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.{{cite web}}: CS1 maint: multiple names: authors list (link)
  3. ^ Merris, Russell (2003). Combinatorics (2nd ed.). Hoboken, N.J.: Wiley-Interscience. p. 45. ISBN 0-471-45849-X. OCLC 53121765.

External links

This page was last edited on 2 February 2024, at 14:00
Basis of this page is in Wikipedia. Text is available under the CC BY-SA 3.0 Unported License. Non-text media are available under their specified licenses. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc. WIKI 2 is an independent company and has no affiliation with Wikimedia Foundation.