1. Not finding help here? Sign up for a free 30min 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!

Combinatorics Proof

  1. Aug 28, 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? I know that n! = n(n-1)!. Any replies would be greatly appreciated.

    Thanks a lot
    Last edited: Aug 28, 2004
  2. jcsd
  3. Aug 28, 2004 #2
    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--
  4. Aug 28, 2004 #3
    Hello courtigrad.

    To prove it, just remember the defintion of C,

    [tex] C_{k-1}^{n} + C_{k}^{n} [/tex]
    [tex] = \frac {n!} {(k-1)!(n-k+1)!} + \frac {n!}{k!(n-k)!} [/tex]
    [tex] = \frac {n!k} {k!(n-k+1)!} + \frac {n!(n-k+1)}{k!(n-k+1)!} [/tex]
    [tex] = \frac {n!}{k!(n+1-k)!} (k+n-k+1) [/tex]
    [tex] = C_{k}^{n+1} [/tex]

    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).
  5. Aug 28, 2004 #4
    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!
  6. Aug 28, 2004 #5


    User Avatar
    Science Advisor
    Homework Helper

    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).
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Combinatorics Proof
  1. Proof required (Replies: 6)

  2. Direct Proof (Replies: 1)

  3. Problem with Proof (Replies: 3)

  4. Intro to proofs (Replies: 6)

  5. Proof help (Replies: 1)