# Homework Help: Combinatorics Proof

1. Aug 26, 2004

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? Any replies would be greatly appreciated.

Thanks a lot

2. Aug 26, 2004

### Gokul43201

Staff Emeritus
Use the definition of nCk in terms of factorials. Use the fact that n! = n(n-1)! OR alternatively, (n+1)! = (n+1)n!. Start from the LHS and don't stop till you get the RHS