Combinatorial Proof: Solving (n C k)= (n-1 C k) + (n-1 C k-1)

[Big-oh]

Homework Statement

Consider the identity:

(n C k) = (n-1 C k) + (n-1 C k-1)

*C means choose. So (n C k) is just n choose k.

Give a combinatorial proof of this identity.The left side means counting the number of ways of choosing k-elements from an n-element list.

But the right side means counting the number of ways of choosing k-elements from an n-1-element list, and adding that to counting the number of ways of choosing k-1-elements from an n-1-element list. I don't see how this relates to the left side.

I have a feeling I just need to partition the right side correctly, but I don't know how I would do it... No full solutions required, a small hint would be fine :D

 

[praharmitra]

Label the n objects 1,2,3,...,n. Consider object no. 1.

LHS = no. of ways to choose k of these n objects

For RHS, consider the following argument. In each choice of k objects either object no. 1 is there or it isn't. Consider both cases separately.

 

[Big-oh]

I think I might have it, I'm just going to use object number n, because it seems to make more sense to me.

Alright so for the RHS:

If S represents the subsets that (n-1 C k) counts, all the elements in S should intersect with the left-side.

Now. In (n-1 C k), any subset in (n C k) that included the object number n wasn't counted (Because it wasn't present), so to "make up" for that, we have to find the ways we can count k-elements in a n-element list, but since object number n always has to be present (To make up for it), we only pick from an n-1-element list.

Is this correct?

 

[praharmitra]

that's correct.

 

[joey9]

Sorry to raise this up so late.

I just had this on a test and didn't get it.
I still don't understand how one is supposed to prove it by induction.

Any help?