# Difference between revisions of "Combinatorial identity"

(it's a theorem) |
(categorize) |
||

Line 1: | Line 1: | ||

− | + | ||

==Hockey-Stick Identity== | ==Hockey-Stick Identity== | ||

For <math>n,r\in\mathbb{N}, n>r,\sum^n_{i=r}{i\choose r}={n+1\choose r+1}</math>. | For <math>n,r\in\mathbb{N}, n>r,\sum^n_{i=r}{i\choose r}={n+1\choose r+1}</math>. | ||

Line 38: | Line 38: | ||

[[Category:Theorems]] | [[Category:Theorems]] | ||

+ | |||

+ | [[Category:Combinatorics]] |

## Revision as of 13:35, 8 December 2007

## Hockey-Stick Identity

For .

This identity is known as the *hockey-stick* identity because, on Pascal's triangle, when the addends represented in the summation and the sum itself are highlighted, a hockey-stick shape is revealed.

*An image is supposed to go here. You can help us out by creating one and editing it in. Thanks.*

### Proof

This identity can be proven by induction on .

__Base case__
Let .

.

__Inductive step__
Suppose, for some , .
Then .

It can also be proven algebraicly with pascal's identity

Look at It can be rewritten as Using pascals identity, we get We can continuously apply pascals identity until we get to