Difference between revisions of "Combinatorial identity"

(yay! hockey-stick picture!)
(Hockey-Stick Identity)
Line 1: Line 1:
==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>.
 
 
<asy>
 
int chew(int n,int r){
 
int res=1;
 
for(int i=0;i<r;++i){
 
  res=quotient(res*(n-i),i+1);
 
  }
 
return res;
 
}
 
for(int n=0;n<9;++n){
 
for(int i=0;i<=n;++i){
 
  if((i==2 && n<8)||(i==3 && n==8)){
 
  if(n==8){label(string(chew(n,i)),(11+n/2-i,-n),p=red+2.5);}
 
  else{label(string(chew(n,i)),(11+n/2-i,-n),p=blue+2);}
 
  }
 
  else{
 
  label(string(chew(n,i)),(11+n/2-i,-n));
 
  }
 
  }
 
}
 
</asy>
 
 
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.
 
 
 
===Proof===
 
 
'''Inductive Proof'''
 
 
This identity can be proven by induction on <math>n</math>.
 
 
<u>Base Case</u>
 
Let <math>n=r</math>.
 
 
<math>\sum^n_{i=r}{i\choose r}=\sum^r_{i=r}{i\choose r}={r\choose r}=1={r+1\choose r+1}</math>.
 
 
<u>Inductive Step</u>
 
Suppose, for some <math>k\in\mathbb{N}, k>r</math>, <math>\sum^k_{i=r}{i\choose r}={k+1\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>.
 
 
'''Algebraic Proof'''
 
 
It can also be proven algebraically with [[Pascal's Identity]], <math>{n \choose k}={n-1\choose k-1}+{n-1\choose k}</math>.
 
Note that
 
 
<math>{r \choose r}+{r+1 \choose r}+{r+2 \choose r}+\cdots+{r+a \choose r}</math>
 
<math>={r+1 \choose r+1}+{r+1 \choose r}+{r+2 \choose r}+\cdots+{r+a \choose r}</math>
 
<math>={r+2 \choose r+1}+{r+2 \choose r}+\cdots+{r+a \choose r}=\cdots={r+a \choose r-1}+{r+a \choose r}={r+a+1 \choose r+1}</math>, which is equivalent to the desired result.
 
 
'''Combinatorial Proof'''
 
 
Imagine that we are distributing <math>n</math> indistinguishable candies to <math>k</math> distinguishable children. By a direct application of Balls and Urns, there are <math>{n+k-1\choose k-1}</math> ways to do this. Alternatively, we can first give <math>0\le i\le n</math> candies to the oldest child so that we are essentially giving <math>n-i</math> candies to <math>k-1</math> kids and again, with Balls and Urns, <math>{n+k-1\choose k-1}=\sum_{i=0}^n{n+k-2-i\choose k-2}</math>, which simplifies to the desired result.
 
 
 
==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>.
 
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>.

Revision as of 13:38, 3 August 2010

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

Another Identity

\[\sum_{i=0}^k \binom{k}{i}^2=\binom{2k}{k}\]

Hat Proof

We have $2k$ different hats. We split them into two groups, each with k hats: then we choose $i$ hats from the first group and $k-i$ hats from the second group. This may be done in $\binom{k}{i}^2$ ways. Evidently, to generate all possible choices of $k$ hats from the $2k$ hats, we must choose $i=0,1,\cdots,k$ hats from the first $k$ and the remaining $k-i$ hats from the second $k$; the sum over all such $i$ is the number of ways of choosing $k$ hats from $2k$. Therefore $\sum_{i=0}^k \binom{k}{i}^2=\binom{2k}{k}$, as desired.

Examples

See also

Invalid username
Login to AoPS