Difference between revisions of "Combinatorial identity"

Revision as of 20:40, 10 February 2009

Hockey-Stick Identity

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

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 $n$ .

Base case Let $n=r$ .

$\sum^n_{i=r}{i\choose r}=\sum^r_{i=r}{i\choose r}={r\choose r}=1={r+1\choose r+1}$ .

Inductive step Suppose, for some $k\in\mathbb{N}, k>r$ , $\sum^k_{i=r}{i\choose r}={k+1\choose r+1}$ . Then $\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}$ .

It can also be proven algebraicly with pascal's identity

Look at ${r \choose r}+{r+1 \choose r} +{r+2 \choose r}...+{r+a \choose r}$ It can be rewritten as ${r+1 \choose r+1}+{r+1 \choose r} +{r+2 \choose r}...+{r+a \choose r}$ Using pascals identity, we get ${r+2 \choose r+1}+{r+2 \choose r}+...+{r+a \choose r}$ We can continuously apply pascals identity until we get to ${r+a \choose r-1}+{r+a \choose r}={r+a+1 \choose r+1}$

Vandermonde's Identity

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

Examples

AIME 2000II/7

@@ Line 28: / Line 28: @@
 ==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 ==

Page

Toolbox

Search