Difference between revisions of "Combinatorial identity"

Latest revision as of 22:47, 27 October 2024

Pascal's Identity

Pascal's Identity states that

${n \choose k}={n-1\choose k-1}+{n-1\choose k}$

for any positive integers $k$ and $n$ . Here, $\binom{n}{k}$ is the binomial coefficient $\binom{n}{k} = {}_nC_k = C_k^n$ .

This result can be interpreted combinatorially as follows: the number of ways to choose $k$ things from $n$ things is equal to the number of ways to choose $k-1$ things from $n-1$ things added to the number of ways to choose $k$ things from $n-1$ things.

Proof

If $k > n$ then $\binom{n}{k} = 0 = \binom{n - 1}{k - 1} + \binom{n - 1}{k}$ and so the result is trivial. So assume $k \leq n$ . Then

$\begin{eqnarray*}\binom{n-1}{k-1}+\binom{n-1}{k}&=&\frac{(n-1)!}{(k-1)!(n-k)!}+\frac{(n-1)!}{k!(n-k-1)!}\\ &=&(n-1)!\left(\frac{k}{k!(n-k)!}+\frac{n-k}{k!(n-k)!}\right)\\ &=&(n-1)!\cdot \frac{n}{k!(n-k)!}\\ &=&\frac{n!}{k!(n-k)!}\\ &=&\binom{n}{k}. \qquad\qquad\square\end{eqnarray*}$

Alternate Proofs

Here, we prove this using committee forming.

Consider picking one fixed object out of $n$ objects. Then, we can choose $k$ objects including that one in $\binom{n-1}{k-1}$ ways.

Because our final group of objects either contains the specified one or doesn't, we can choose the group in $\binom{n-1}{k-1}+\binom{n-1}{k}$ ways.

But we already know they can be picked in $\binom{n}{k}$ ways, so

${n \choose k}={n-1\choose k-1}+{n-1\choose k}$

Also, we can look at Pascal's Triangle to see why this is. If we were to extend Pascal's Triangle to row n, we would see the term $\binom{n}{k}$ . Above that, we would see the terms ${n-1\choose k-1}$ and ${n-1\choose k}$ . Due to the definition of Pascal's Triangle, ${n \choose k}={n-1\choose k-1}+{n-1\choose k}$ .

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

Combinatorial Proof

Think of the right hand side as picking $r$ people from $m$ men and $n$ women. Think of the left hand side as picking $k$ men from the $m$ total men and picking $r-k$ women from the $n$ total women. The left hand side and right hand side are the same, thus Vandermonde's identity must be true.

~avn

Algebraic proof

For all $x,$ $(1+x)^m(1+x)^n = (1+x)^{m+n}$ The coefficients of $x^r$ on both sides must be the same, so using the Binomial Theorem, $\sum_{k=0}^r \binom mk \binom n{r-k} = \binom {m+n}r.$

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. We can also flip the hockey stick because pascal's triangle is symmetrical.

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 Urns, 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 Urns, ${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.

Algebraic Proof 3

Consider the number of solutions to the equation $a_1$ + $a_2$ + $a_3$ + $a_4$ + $a_5$ + $a_6$ +.......+ $a_r$ ≤ N where each $a_i$ is a non-negative integer for 1≤i≤r.

METHOD 1 We know since all numbers on LHS are non-negative therefore 0≤N and N is a integer.

Therfore, $a_1$ + $a_2$ + $a_3$ + $a_4$ + $a_5$ + $a_6$ +.......+ $a_r$ = 0,1,2......N. Consider each case seperately.

$a_1$ + $a_2$ + $a_3$ + $a_4$ + $a_5$ + $a_6$ +.......+ $a_r$ =0 by Stars-and-bars the equation has $\binom {0+r-1}{r-1}$ solutions.

$a_1$ + $a_2$ + $a_3$ + $a_4$ + $a_5$ + $a_6$ +.......+ $a_r$ =1 by Stars-and-bars the equation has $\binom {1+r-1}{r-1}$ solutions.

$a_1$ + $a_2$ + $a_3$ + $a_4$ + $a_5$ + $a_6$ +.......+ $a_r$ =2 by Stars-and-bars the equation has $\binom {2+r-1}{r-1}$ solutions.

........... $a_1$ + $a_2$ + $a_3$ + $a_4$ + $a_5$ + $a_6$ +.......+ $a_r$ =N by Stars-and-bars the equation has $\binom {N+r-1}{r-1}$ solutions.

Hence, the equation has $\binom {r-1}{r-1}$ + $\binom {r}{r-1}$ + $\binom {r+1}{r-1}$ +.... $\binom {N+r-1}{r-1}$ = $\sum^k_{i=r-1}{i\choose r-1}$ (where k=N+r-1) SOLUTIONS.

METHOD 2 Since, $a_1$ + $a_2$ + $a_3$ + $a_4$ + $a_5$ + $a_6$ +.......+ $a_r$ ≤ N Therefore we may say $a_1$ + $a_2$ + $a_3$ + $a_4$ + $a_5$ + $a_6$ +.......+ $a_r$ = N -m where m is another non-negative integer. 0 ≤ $a_1$ + $a_2$ + $a_3$ + $a_4$ + $a_5$ + $a_6$ +.......+ $a_r$ ⇒ 0≤ N-m ⇒ m≤ N So, we need not count this as an extra restriction.

Now, $a_1$ + $a_2$ + $a_3$ + $a_4$ + $a_5$ + $a_6$ +.......+ $a_r$ +m = N. Again by Stars-and-bars this has $\binom {N+r}{r}$ solutions.

Therefore, the equation has $\binom {N+r}{r}$ = $\binom {k+1}{r}$ solutions(As N+r-1 =k).

Since, both methods yeild the same answer ⇒ $\sum^k_{i=r-1}{i\choose r-1}$ = $\binom {k+1}{r}$ . Taking r-1= p redirects to the honeystick identity.

~SANSGANKRSNGUPTA

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

Even Odd Identity

$\sum_{k=0}^m (-1)^k \binom{n}{k}= (-1)^m \binom{n-1}{m}$

@@ Line 1: / Line 1: @@
+== Pascal's Identity ==
+Pascal's Identity states that
+<math>{n \choose k}={n-1\choose k-1}+{n-1\choose k}</math>
+for any [[positive integer]]s <math>k</math> and <math>n</math>.  Here, <math>\binom{n}{k}</math> is the binomial coefficient <math>\binom{n}{k} = {}_nC_k = C_k^n</math>.
+This result can be interpreted combinatorially as follows: the number of ways to choose <math>k</math> things from <math>n</math> things is equal to the number of ways to choose <math>k-1</math> things from <math>n-1</math> things added to the number of ways to choose <math>k</math> things from <math>n-1</math> things.
+=== Proof ===
+If <math>k > n</math> then <math>\binom{n}{k} = 0 = \binom{n - 1}{k - 1} + \binom{n - 1}{k}</math> and so the result is trivial.  So assume <math>k \leq n</math>.  Then
+<cmath>\begin{eqnarray*}\binom{n-1}{k-1}+\binom{n-1}{k}&=&\frac{(n-1)!}{(k-1)!(n-k)!}+\frac{(n-1)!}{k!(n-k-1)!}\\
+&=&(n-1)!\left(\frac{k}{k!(n-k)!}+\frac{n-k}{k!(n-k)!}\right)\\
+&=&(n-1)!\cdot \frac{n}{k!(n-k)!}\\
+&=&\frac{n!}{k!(n-k)!}\\
+&=&\binom{n}{k}. \qquad\qquad\square\end{eqnarray*}</cmath>
+===Alternate Proofs===
+Here, we prove this using [[committee forming]].
+Consider picking one fixed object out of <math>n</math> objects. Then, we can choose <math>k</math> objects including that one in <math>\binom{n-1}{k-1}</math> ways.
+Because our final group of objects either contains the specified one or doesn't, we can choose the group in <math>\binom{n-1}{k-1}+\binom{n-1}{k}</math> ways.
+But we already know they can be picked in <math>\binom{n}{k}</math> ways, so
+<cmath>{n \choose k}={n-1\choose k-1}+{n-1\choose k} </cmath>
+Also, we can look at Pascal's Triangle to see why this is. If we were to extend Pascal's Triangle to row n, we would see the term <math>\binom{n}{k}</math>. Above that, we would see the terms <math>{n-1\choose k-1}</math> and <math>{n-1\choose k}</math>. Due to the definition of Pascal's Triangle, <math>{n \choose k}={n-1\choose k-1}+{n-1\choose k}</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>.
+===Video Proof===
+https://www.youtube.com/watch?v=u1fktz9U9ig
+===Combinatorial Proof===
+Think of the right hand side as picking <math>r</math> people from <math>m</math> men and <math>n</math> women. Think of the left hand side as picking <math>k</math> men from the <math>m</math> total men and picking <math>r-k</math> women from the <math>n</math> total women. The left hand side and right hand side are the same, thus Vandermonde's identity must be true.
+~avn
+===Algebraic proof===
+For all <math>x,</math> <cmath>(1+x)^m(1+x)^n = (1+x)^{m+n}</cmath>
+The coefficients of <math>x^r</math> on both sides must be the same, so using the [[Binomial Theorem]], <cmath>\sum_{k=0}^r \binom mk \binom n{r-k} = \binom {m+n}r.</cmath>
 ==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>.
@@ Line 25: / Line 72: @@
 </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.
+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. We can also flip the hockey stick because pascal's triangle is symmetrical.
@@ Line 59: / Line 106: @@
 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.
+'''Algebraic Proof 3'''
+Consider the number of solutions to the equation <math>a_1</math>+<math>a_2</math>+<math>a_3</math>+<math>a_4</math>+<math>a_5</math>+<math>a_6</math>+.......+<math>a_r</math> ≤ N where each <math>a_i</math> is a
+non-negative integer for 1≤i≤r.
+'''METHOD 1'''
+We know since all numbers on LHS are non-negative therefore 0≤N and N is a integer.
+Therfore, <math>a_1</math>+<math>a_2</math>+<math>a_3</math>+<math>a_4</math>+<math>a_5</math>+<math>a_6</math>+.......+<math>a_r</math> = 0,1,2......N. Consider each case seperately.
+<math>a_1</math>+<math>a_2</math>+<math>a_3</math>+<math>a_4</math>+<math>a_5</math>+<math>a_6</math>+.......+<math>a_r</math> =0 by [[Stars-and-bars]] the equation has <math>\binom {0+r-1}{r-1}</math> solutions.
+<math>a_1</math>+<math>a_2</math>+<math>a_3</math>+<math>a_4</math>+<math>a_5</math>+<math>a_6</math>+.......+<math>a_r</math> =1 by [[Stars-and-bars]] the equation has <math>\binom {1+r-1}{r-1}</math> solutions.
+<math>a_1</math>+<math>a_2</math>+<math>a_3</math>+<math>a_4</math>+<math>a_5</math>+<math>a_6</math>+.......+<math>a_r</math> =2 by [[Stars-and-bars]] the equation has <math>\binom {2+r-1}{r-1}</math> solutions.
+...........
+<math>a_1</math>+<math>a_2</math>+<math>a_3</math>+<math>a_4</math>+<math>a_5</math>+<math>a_6</math>+.......+<math>a_r</math> =N by [[Stars-and-bars]] the equation has <math>\binom {N+r-1}{r-1}</math> solutions.
+Hence, the equation has <math>\binom {r-1}{r-1}</math>+ <math>\binom {r}{r-1}</math>+ <math>\binom {r+1}{r-1}</math>+.... <math>\binom {N+r-1}{r-1}</math>= <math>\sum^k_{i=r-1}{i\choose r-1}</math> (where k=N+r-1) SOLUTIONS.
+'''METHOD 2'''
+Since, <math>a_1</math>+<math>a_2</math>+<math>a_3</math>+<math>a_4</math>+<math>a_5</math>+<math>a_6</math>+.......+<math>a_r</math> ≤ N Therefore we may say <math>a_1</math>+<math>a_2</math>+<math>a_3</math>+<math>a_4</math>+<math>a_5</math>+<math>a_6</math>+.......+<math>a_r</math> = N -m  where m is another non-negative integer.
+≤<math>a_1</math>+<math>a_2</math>+<math>a_3</math>+<math>a_4</math>+<math>a_5</math>+<math>a_6</math>+.......+<math>a_r</math> ⇒ 0≤ N-m ⇒ m≤ N  So, we need not count this as an extra restriction.
+Now, <math>a_1</math>+<math>a_2</math>+<math>a_3</math>+<math>a_4</math>+<math>a_5</math>+<math>a_6</math>+.......+<math>a_r</math> +m = N. Again by [[Stars-and-bars]] this has <math>\binom {N+r}{r}</math> solutions.
+Therefore, the equation has <math>\binom {N+r}{r}</math> = <math>\binom {k+1}{r}</math>  solutions(As N+r-1 =k).
+Since, both methods yeild the same answer ⇒''' <math>\sum^k_{i=r-1}{i\choose r-1}</math> = <math>\binom {k+1}{r}</math>'''. Taking r-1= p redirects to the honeystick identity.
+~SANSGANKRSNGUPTA
 ==Another Identity==
@@ Line 70: / Line 156: @@
 ===Proof 2===
-This is a special case of Vandermonde's identity, in which we set <math>m=n</math> and <math>r=m</math>.
+This is a special case of Vandermonde's identity, in which we set <math>m=n=r</math>.
+== Even Odd Identity ==
+<cmath>
+\sum_{k=0}^m (-1)^k \binom{n}{k}= (-1)^m \binom{n-1}{m}
+</cmath>
 == 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 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)]
+* [https://artofproblemsolving.com/wiki/index.php?title=2013_AIME_I_Problems/Problem_6#Solution_2 2013 AIME I Problem 6 (Solution 2)]
 * [http://artofproblemsolving.com/wiki/index.php/2015_AIME_I_Problems/Problem_12 2015 AIME I Problem 12]
+* [http://artofproblemsolving.com/wiki/index.php/2018_AIME_I_Problems/Problem_10 2018 AIME I Problem 10]
+* [https://artofproblemsolving.com/wiki/index.php/2020_AIME_I_Problems/Problem_7 2020 AIME I Problem 7]
+* [https://artofproblemsolving.com/wiki/index.php/2016_AMC_10A_Problems/Problem_20 2016 AMC 10A Problem 20]
+* [https://artofproblemsolving.com/wiki/index.php/2021_AMC_12A_Problems/Problem_15 2021 AMC 12A  Problem 15]
+* [https://artofproblemsolving.com/wiki/index.php/1981_IMO_Problems 1981 IMO Problem 2]
+* [https://artofproblemsolving.com/wiki/index.php/2022_AIME_I_Problems/Problem_12  2022 AIME I Problem 12 ]
 ==See also==
 * [[Pascal's Triangle]]
 * [[Combinatorics]]
+* [[Pascal's Identity]]
 [[Category:Theorems]]
 [[Category:Combinatorics]]

Page

Toolbox

Search

Difference between revisions of "Combinatorial identity"

Latest revision as of 22:47, 27 October 2024

Contents

Pascal's Identity

Proof

Alternate Proofs

Vandermonde's Identity

Video Proof

Combinatorial Proof

Algebraic proof

Hockey-Stick Identity

Proof

Another Identity

Hat Proof

Proof 2

Even Odd Identity

Examples

See also