Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Combinatorics Proof

  1. Aug 26, 2004 #1
    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. jcsd
  3. Aug 26, 2004 #2

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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 :biggrin:
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook