# Difference between revisions of "Combinatorial identity"

(Another proof of the hockey stick identity) |
(Fixing latex) |
||

Line 19: | Line 19: | ||

Then <math>\sum^{k+1}_{i=r}{i\choose r}=\left(\sum^k_{i=r}{i\choose r}\right)+{k+1\choose r}={k+1\choose r+1}+{k+1\choose r}={k+2\choose r+1}</math>. | Then <math>\sum^{k+1}_{i=r}{i\choose r}=\left(\sum^k_{i=r}{i\choose r}\right)+{k+1\choose r}={k+1\choose r+1}+{k+1\choose r}={k+2\choose r+1}</math>. | ||

− | It can also be proven algebraicly with pascal's identity <math> | + | It can also be proven algebraicly with pascal's identity |

− | Look at <math> | + | <math>{n \choose k}={n-1\choose k-1}+{n-1\choose k}</math> |

− | It can be rewritten as <math> | + | Look at <math> {r \choose r}+{r+1 \choose r} +{r+2 \choose r}...+{r+a \choose r}</math> |

− | Using pascals identity, we get <math> | + | It can be rewritten as <math> {r+1 \choose r+1}+{r+1 \choose r} +{r+2 \choose r}...+{r+a \choose r}</math> |

+ | Using pascals identity, we get <math>{r+2 \choose r+1}+{r+2 \choose r}+...+{r+a \choose r}</math> | ||

We can continuously apply pascals identity until we get to | We can continuously apply pascals identity until we get to | ||

− | <math> | + | <math>{r+a \choose r-1}+{r+a \choose r}={r+a+1 \choose r+1}</math> |

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

## Revision as of 20:26, 29 October 2006

*This article is a stub. Help us out by expanding it.*

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