1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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


    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

Similar Threads for Combinatorics Proof Date
Proof of Wheatstone bridge equation Dec 26, 2017
Entropy and combinatorics May 11, 2014
Combinatorics-next problem with numbers Sep 15, 2005
Combinatorics Problem Apr 10, 2005
Combinatorics problem Feb 15, 2005