Math 2.0

Combinatorics Theorem

Hockey-stick identity

Builds on Binomial coefficient

Statement

Let nn and rr be natural numbers with r≤nr \le n. Then ∑i=rn(ir)=(n+1r+1).\sum_{i=r}^{n} \binom{i}{r} = \binom{n + 1}{r + 1}.

Remarks

For r=1r = 1 it gives 1+2+⋯+n=(n+12)=n(n+1)21 + 2 + \dots + n = \binom{n+1}{2} = \frac{n(n+1)}{2}. Combinatorial proof: classify the (r+1)(r+1)-subsets of {1,…,n+1}\{1, \dots, n + 1\} by their largest element i+1i + 1. The other rr elements come from {1,…,i}\{1, \dots, i\}. In Pascal's triangle the summands lie on a diagonal, and the result lies below the end of the diagonal. This shape is the reason for the name.

Reading path

To understand this page from the ground up, read these 2 pages in order. The foundations come first.

Show the path as a graph
Binomial coefficient, definition, no evidence levelBinomial coefficientdefinitionHockey-stick identity, statement, no evidence levelHockey-stick identitystatement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Binomial coefficient definition
  2. Hockey-stick identity statement

Further reading

  1. Web https://en.wikipedia.org/wiki/Hockey-stick_identity, Formulations
About this page
Tag04JHQNNBFE
URIm2://04JHQNNBFE
Kindstatement, theorem
WritingW1 stated
MSC05A19
StatusThis copy of the site has no build data. Run m2 status 04JHQNNBFE.
UsesBinomial coefficient
Same as

Markdown · JSON · Edit on GitHub

What this page needs for W2

  • edge about out: the concepts that the statement is about (0 of 1)
  • edge proves in: at least one proof node (0 of 1)
  • edge instance_of or illustrates in: one example that shows the statement at work (0 of 1)
  • explanation L2 (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.