# Difference between revisions of "Combinatorial identity"

(categorize) |
(→Vandermonde's Identity) |
||

Line 28: | Line 28: | ||

==Vandermonde's Identity== | ==Vandermonde's Identity== | ||

+ | Vandermonde's Identity states that <math>\sum_{k=0}^r\binom mk\binom n{r-k}=\binom{m+n}r</math>, which can be proven combinatorially by noting that any combination of <math>r</math> objects from a group of <math>m+n</math> objects must have some <math>0\le k\le r</math> objects from group <math>m</math> and the remaining from group <math>n</math>. | ||

== Examples == | == Examples == |

## Revision as of 20:40, 10 February 2009

## 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

## Vandermonde's Identity

Vandermonde's Identity states that , which can be proven combinatorially by noting that any combination of objects from a group of objects must have some objects from group and the remaining from group .