Thread: combinations proof

To prove a combinations equality:

(n+2 C r+1) = (n C r+1) + 2 (n C r ) + (n C r-1)

-> (n+2 C r+1) = (n+2)! / (n+2 - (r+1))! (r+1)!

-> (n C r+1) = n! / (n - (r+1))! (r+1)!

-> 2 (n C r ) = 2n! / (n - r)! r!

-> (n C r-1) = n! / (n - (r-1))! (r-1)!


Then I got this:

(n+2)! / (n - r + 1)! (r+1)!

= [n! / (n - r - 1)! (r+1)!] + [2n! / (n - r)! r!] + [n! / (n - r + 1)! (r-1)!]

Any help from here will be greatly appreciated. can get a common denominator, but I am wondering if there is a better/quicker approach.

The way you're doing it will certainly work.

Here's another way.

We want to show that the left side counts the same number of things as the right side.

is the number of ways to choose a subset of size from the set .

There are 4 cases.

We can choose a subset that contains neither nor . This can be done in , as we're now choosing a size subset from the set .

We can choose a subset that contains but not .
This can be done in ways, as we are now choosing size subsets from the set .

Similarly, we can choose a subset that contains but not in ways.

Finally. we can choose a subset that contains both and . This can be done in ways.

Add the 4 cases and we have the desired result.