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