YAMathT: What's a combinatorial argument?

[Syringer]

Question:

The following identity is known as Fermat's combinatorial identity?

(n k) = sum from i = k to n (i-1 k-1) n >= k

(n k) denotes a combination, i.e. n choose k, similar to (i-1 k-1)

Give a combinatorial argument (no computations are needed) to establish this identity.

Hint: Consider the set of numbers 1 throug n. How many subsets of size k have i as their highest-numbered member?

 

[Syringer]

?

 

[TuxDave]

I would guess it's a proof of words like the total combination will be the sum of all the possibilities. Of course.. with a little more detail.

How many subsets of size k have i as their highest-numbered member?

So one number in the subset is the number i. You have i-1 numbers to pick k-1 numbers.

So the numbers of size k which have i as their highest number is (i-1 k-1)

That's hint #1.... want hint #2?

 

[Syringer]

Hint #2 would be nice

 

[TuxDave]

Originally posted by: Syringer
Hint #2 would be nice

Using that numbers 1 to n thing..

(n k) has you picking a subset of size k from n numbers...

You can separate those subsets into groups based on the highest number in the subset.

For example, all these subsets over here will have 5 as their largest number.
All those subsets over here will have 7 as their largest number
etc....

No subset can fall in two groups, and the subset is bound to fall in some group. If you take all the groups and add it together, you'll get all the possibilities of (n k)

It's late... I hope it makes sense.

 

[chuckywang]

TuxDave is absolutely right.
How about this:

Let's see what happens with (6 3) as an example. This denotes the number ways to choose 3 numbers from the set (1, 2, 3, 4, 5, 6).

From the identity: (6 3) = (2 2) + (3 2)+(4 2)+(5 2)

How many ways can we choose 3 numbers such that 3 is the largest number? Well, if 3 is the largest number, then you have to pick 2 more numbers out of the set (1, 2), i.e. (2 2) ways.

How many ways can we choose 3 numbers such that 4 is the largest number? Well, if 4 is the largest number, then you have to pick 2 more numbers out of the set (1, 2, 3), .e. (3 2) ways.

How many ways can we choose 3 numbers such that 5 is the largest number? Well, if 5 is the largest number, then you have to pick 2 more numbers out of the set (1, 2, 3, 4), i.e. (4 2) ways.

How many ways can we choose 3 numbers such that 6 is the largest number? Well, if 6 is the largest number, then you have to pick 2 more numbers out of the set (1, 2, 3, 4, 5), i.e. (5 2) ways.

Therefore, From the identity: (6 3) = (2 2) + (3 2)+(4 2)+(5 2) since all those ways we chose subsets are mutually exclusive.
Hopefully, this will shed some light on the problem.

Whew, that was a lot of copying-pasting.

 

[Syringer]

Ahh, you guys are awesome, it took me a few times to read over what you guys wrote but I eventually got it.