Difference between revisions of "Combinatorial identity"

(Vandermonde's Identity)
m (Proof)
 
(30 intermediate revisions by 17 users not shown)
Line 1: Line 1:
 +
==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>.
 +
 +
===Video Proof===
 +
 +
https://www.youtube.com/watch?v=u1fktz9U9ig
 +
 +
~avn
  
 
==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>.
  
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.
+
<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 is highlighted, a hockey-stick shape is revealed.
  
{{image}}
 
  
 
===Proof===
 
===Proof===
 +
 +
'''Inductive Proof'''
 +
 
This identity can be proven by induction on <math>n</math>.
 
This identity can be proven by induction on <math>n</math>.
  
<u>Base case</u>
+
<u>Base Case</u>
 
Let <math>n=r</math>.
 
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>.
 
<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>
+
<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>.
 
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>.
 
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
+
'''Algebraic Proof'''
<math>{n \choose k}={n-1\choose k-1}+{n-1\choose k}</math>
+
 
Look at <math> {r \choose r}+{r+1 \choose r} +{r+2 \choose r}...+{r+a \choose r}</math>
+
It can also be proven algebraically with [[Pascal's Identity]], <math>{n \choose k}={n-1\choose k-1}+{n-1\choose k}</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>
+
Note that
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  
+
<math>{r \choose r}+{r+1 \choose r}+{r+2 \choose r}+\cdots+{r+a \choose r}</math>
<math>{r+a \choose r-1}+{r+a \choose r}={r+a+1 \choose r+1}</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 1'''
 +
 
 +
Imagine that we are distributing <math>n</math> indistinguishable candies to <math>k</math> distinguishable children. By a direct application of Balls and Holes, 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 Holes, <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.
 +
 
 +
'''Combinatorial Proof 2'''
 +
 
 +
We can form a committee of size <math>k+1</math> from a group of <math>n+1</math> people in <math>{{n+1}\choose{k+1}}</math> ways. Now we hand out the numbers <math>1,2,3,\dots,n-k+1</math> to <math>n-k+1</math> of the <math>n+1</math> people.  We can divide this into <math>n-k+1</math> disjoint cases.  In general, in case <math>x</math>, <math>1\le x\le n-k+1</math>, person <math>x</math> is on the committee and persons <math>1,2,3,\dots, x-1</math> are not on the committee.  This can be done in <math>\binom{n-x+1}{k}</math> ways.  Now we can sum the values of these <math>n-k+1</math> disjoint cases, getting <cmath>{{n+1}\choose {k+1}} ={{n}\choose{k}}+{{n-1}\choose{k}}+{{n-2}\choose{k}}+\hdots+{{k+1}\choose{k}}+{{k}\choose{k}}.</cmath>
 +
 
 +
'''Algebraic Proof 2'''
 +
 
 +
Apply the finite geometric series formula to <math>(1+x)</math>: <cmath>1+(1+x)+(1+x)^2+...+(1+x)^n=\frac{(1+x)^{n+1}-1}{(1+x)-1}</cmath> Then expand with the Binomial Theorem and simplify: <cmath>1+(1+x)+(1+2x+x^2)+...+ \left (\binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+...+\binom{n}{n-1}x^{n-1}+\binom{n}{n}x^n \right )=\binom{n+1}{1}+\binom{n+1}{2}x+...+\binom{n+1}{n+1}x^n</cmath> Finally, equate coefficients of <math>x^m</math> on both sides: <cmath>\binom{0}{m}+\binom{1}{m}+\binom{2}{m}+...+\binom{n}{m}=\binom{n+1}{m+1}</cmath> Since for <math>i<m</math>, <math>\binom{i}{m}=0</math>, this simplifies to the hockey stick identity. -- EVIN-
 +
 
 +
==Another Identity==
 +
 
 +
<cmath>
 +
\sum_{i=0}^k \binom{k}{i}^2=\binom{2k}{k}
 +
</cmath>
 +
 
 +
===Hat Proof===
 +
We have <math>2k</math> different hats. We split them into two groups, each with k hats: then we choose <math>i</math> hats from the first group and <math>k-i</math> hats from the second group. This may be done in <math>\binom{k}{i}^2</math> ways. Evidently, to generate all possible choices of <math>k</math> hats from the <math>2k</math> hats, we must choose <math>i=0,1,\cdots,k</math> hats from the first <math>k</math> and the remaining <math>k-i</math> hats from the second <math>k</math>; the sum over all such <math>i</math> is the number of ways of choosing <math>k</math> hats from <math>2k</math>. Therefore  <math>\sum_{i=0}^k \binom{k}{i}^2=\binom{2k}{k}</math>, as desired.
 +
 
 +
===Proof 2===
 +
This is a special case of Vandermonde's identity, in which we set <math>m=n</math> and <math>r=m</math>.
  
==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 ==
 
+
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=394407#394407 1986 AIME Problem 11]
* [http://www.artofproblemsolving.com/Forum/resources.php?c=182&cid=45&year=2000&p=385891 AIME 2000II/7]
+
* [http://www.artofproblemsolving.com/Forum/resources.php?c=182&cid=45&year=2000&p=385891 2000 AIME II Problem 7]
 +
* [https://artofproblemsolving.com/wiki/index.php?title=2013_AIME_I_Problems/Problem_6#Solution_Two 2013 AIME II Problem 6 (Solution 2)]
 +
* [http://artofproblemsolving.com/wiki/index.php/2015_AIME_I_Problems/Problem_12 2015 AIME I Problem 12]
 +
* [https://artofproblemsolving.com/wiki/index.php/2020_AIME_I_Problems/Problem_7 2020 AIME I Problem 7]
  
 
==See also==
 
==See also==

Latest revision as of 17:11, 6 August 2020

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

Video Proof

https://www.youtube.com/watch?v=u1fktz9U9ig

~avn

Hockey-Stick Identity

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

[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 is highlighted, a hockey-stick shape is revealed.


Proof

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

Algebraic Proof

It can also be proven algebraically with Pascal's Identity, ${n \choose k}={n-1\choose k-1}+{n-1\choose k}$. Note that

${r \choose r}+{r+1 \choose r}+{r+2 \choose r}+\cdots+{r+a \choose r}$ $={r+1 \choose r+1}+{r+1 \choose r}+{r+2 \choose r}+\cdots+{r+a \choose r}$ $={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}$, which is equivalent to the desired result.

Combinatorial Proof 1

Imagine that we are distributing $n$ indistinguishable candies to $k$ distinguishable children. By a direct application of Balls and Holes, there are ${n+k-1\choose k-1}$ ways to do this. Alternatively, we can first give $0\le i\le n$ candies to the oldest child so that we are essentially giving $n-i$ candies to $k-1$ kids and again, with Balls and Holes, ${n+k-1\choose k-1}=\sum_{i=0}^n{n+k-2-i\choose k-2}$, which simplifies to the desired result.

Combinatorial Proof 2

We can form a committee of size $k+1$ from a group of $n+1$ people in ${{n+1}\choose{k+1}}$ ways. Now we hand out the numbers $1,2,3,\dots,n-k+1$ to $n-k+1$ of the $n+1$ people. We can divide this into $n-k+1$ disjoint cases. In general, in case $x$, $1\le x\le n-k+1$, person $x$ is on the committee and persons $1,2,3,\dots, x-1$ are not on the committee. This can be done in $\binom{n-x+1}{k}$ ways. Now we can sum the values of these $n-k+1$ disjoint cases, getting \[{{n+1}\choose {k+1}} ={{n}\choose{k}}+{{n-1}\choose{k}}+{{n-2}\choose{k}}+\hdots+{{k+1}\choose{k}}+{{k}\choose{k}}.\]

Algebraic Proof 2

Apply the finite geometric series formula to $(1+x)$: \[1+(1+x)+(1+x)^2+...+(1+x)^n=\frac{(1+x)^{n+1}-1}{(1+x)-1}\] Then expand with the Binomial Theorem and simplify: \[1+(1+x)+(1+2x+x^2)+...+ \left (\binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+...+\binom{n}{n-1}x^{n-1}+\binom{n}{n}x^n \right )=\binom{n+1}{1}+\binom{n+1}{2}x+...+\binom{n+1}{n+1}x^n\] Finally, equate coefficients of $x^m$ on both sides: \[\binom{0}{m}+\binom{1}{m}+\binom{2}{m}+...+\binom{n}{m}=\binom{n+1}{m+1}\] Since for $i<m$, $\binom{i}{m}=0$, this simplifies to the hockey stick identity. -- EVIN-

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.

Proof 2

This is a special case of Vandermonde's identity, in which we set $m=n$ and $r=m$.


Examples

See also

Invalid username
Login to AoPS