# Difference between revisions of "Combinatorial identity"

(→Examples) |
(→Proof) |
||

Line 59: | Line 59: | ||

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

+ | [list=1] | ||

+ | Apply the finite geometric series formula to <math>(1+x)</math>: <math>1+(1+x)+(1+x)^2+...+(1+x)^n=\frac{(1+x)^{n+1}-1}{(1+x)-1}</math>. Then expand with the Binomial Theorem and simplify: <math>1+(1+x)+(1+2x+x^2)+...+(\binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+...+\binom{n}{n-1}x^{n-1}+\binom{n}{n}x^n)=\binom{n+1}{1}+\binom{n+1}{2}x+...+\binom{n+1}{n+1}x^n</math>. Finally, equate coefficients of <math>x^m</math> on both sides: <math>\binom{0}{m}+\binom{1}{m}+\binom{2}{m}+...+\binom{n}{m}=\binom{n+1}{m+1}</math>. | ||

==Another Identity== | ==Another Identity== |

## Revision as of 17:11, 26 March 2020

## Contents

## Vandermonde's Identity

Vandermonde's Identity states that , which can be proven combinatorially by noting that any combination of objects from a group of objects must have some objects from group and the remaining from group .

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

### Proof

**Inductive Proof**

This identity can be proven by induction on .

__Base Case__
Let .

.

__Inductive Step__
Suppose, for some , .
Then .

**Algebraic Proof**

It can also be proven algebraically with Pascal's Identity, . Note that

, which is equivalent to the desired result.

**Combinatorial Proof 1**

Imagine that we are distributing indistinguishable candies to distinguishable children. By a direct application of Balls and Urns, there are ways to do this. Alternatively, we can first give candies to the oldest child so that we are essentially giving candies to kids and again, with Balls and Urns, , which simplifies to the desired result.

**Combinatorial Proof 2**

We can form a committee of size from a group of people in ways. Now we hand out the numbers to of the people. We can divide this into disjoint cases. In general, in case , , person is on the committee and persons are not on the committee. This can be done in ways. Now we can sum the values of these disjoint cases, getting

**Algebraic Proof 2**
[list=1]
Apply the finite geometric series formula to : . Then expand with the Binomial Theorem and simplify: . Finally, equate coefficients of on both sides: .

## Another Identity

### Hat Proof

We have different hats. We split them into two groups, each with k hats: then we choose hats from the first group and hats from the second group. This may be done in ways. Evidently, to generate all possible choices of hats from the hats, we must choose hats from the first and the remaining hats from the second ; the sum over all such is the number of ways of choosing hats from . Therefore , as desired.

### Proof 2

This is a special case of Vandermonde's identity, in which we set and .

## Examples

- 1986 AIME Problem 11
- 2000 AIME II Problem 7
- 2013 AIME II Problem 6 (Solution 2)
- 2015 AIME I Problem 12
- 2020 AIME I Problem 7