Combinatorics Proof

[courtrigrad]

Hello all

In my calculus book, this problem has been pestering me"

Prove nC(k-1) + nCk = (n+1)Ck, where k > 0 which is read " n choose k-1" + "n choose k"

= n+1C k.

I tried using the formula for the binomial coefficient, but it becomes very messy. I also tried setting k = 1, but then it did not seem like I was actually proving it. Rather I was showing that the statement holds for k > 0. Would I have to use proof my induction? I know that n! = n(n-1)!. Any replies would be greatly appreciated.

Thanks a lot

[Vance]

Just expand the left hand side of the given formula and take out (n+1)!/[k!(n+1-k)!], then you will be left with [k/(n+1)]+[(n-k+1)/(n+1)] which is equal to 1.

You're welcome! --lol--

[Wong]

Hello courtigrad.

To prove it, just remember the defintion of C,

C_{k-1}^{n} + C_{k}^{n}
= \frac {n!} {(k-1)!(n-k+1)!} + \frac {n!}{k!(n-k)!}
= \frac {n!k} {k!(n-k+1)!} + \frac {n!(n-k+1)}{k!(n-k+1)!}
= \frac {n!}{k!(n+1-k)!} (k+n-k+1)
= C_{k}^{n+1}

The equation has a verbal interpretation. To choose k things from n+1 things, we can first take away one thing (call it x) from the n+1 things, leaving n things. Then we may either make x one of our k things to be choosen (and in this case we choose k-1 things from the remaining n things), or exclude x as our choice (and in this case we choose all the k things from the remaining n things).

[courtrigrad]

Thanks a lot guys! That was of great help. Wong I really appreciate how much time you spent writing your solution. It is very elegant!

[Tide]

FWIW - here's another take on the problem: Suppose a set S contains n items. You add one additional item to form a new set S' (containing n+1 items). Now in choosing k items from S' you could choose them all from the original n items in S, C(n, k), or you could choose the item you just added plus k-1 items from the original items, C(n, k-1) so that C(n+1, k) = C(n, k) + C(n, k-1).