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!

Gosh darn combinatorics

  1. Sep 14, 2014 #1
    So look at what Ive done:
    {n+1 \choose k} = \frac {(n+1)!} {(n+1-k)! \cdot k!} = \frac {(n+1)\cdot n!}{(n-(k-1))!\cdot k \cdot (k-1)!}
    \frac {(n+1)}{k}


    \frac { n!}{(n-(k-1))!\cdot (k-1)!} =

    \frac {(n+1)}{k}


    {n \choose k-1}


    oops I accidentally posted this before I finished my calculations, please ignore this until I've finished it. Thanks

    [edit] So Yea, thats it. Thing is, somethings wrong (try plugging numbers into it). Anyways, I need to figure out what I did wrong. This is just part of a massive can of worms. Im trying to figure out the proof for: [tex]

    \sum\limits_{i=1}^n {n \choose k} = 2^n
    Last edited: Sep 14, 2014
  2. jcsd
  3. Sep 14, 2014 #2


    Staff: Mentor

  4. Sep 14, 2014 #3
    Pascals identity to be exact. I've read some "proofs" if you can call them that, but they were rather not helpful. math stack exchange.

    When I replace my summation from k=0 to n, with the combinatorics: [itex]

    \sum_{k=0}^n{n+1 \choose k} =

    \sum_{k=0}^n {n \choose k} +{n \choose k-1}

    [/itex] I have the problem that k-1 will equal -1 in the first iteration of the summation. dont know how to fix this.
  5. Sep 14, 2014 #4


    User Avatar
    Homework Helper

    The lower limit of the sum should be k=0 because i isn't present in the combinatoric and for reasons you'll eventually find out, it should start at 0.

    So you want to prove
    \sum\limits_{k=0}^n {n \choose k} = 2^n

    then simply notice that the binomial expansion is

    [tex](a+b)^n = \sum\limits_{k=0}^n{n\choose k}a^{n-k}b^k[/tex]

    So for what values of a and b is

    [tex]\sum\limits_{k=0}^n{n\choose k}a^{n-k}b^k\equiv \sum\limits_{k=0}^n {n \choose k}[/tex]
  6. Sep 21, 2014 #5
    The problem here is that ##\binom{n+1}k=\binom nk+\binom n{k-1}## only for k>0; if k=0 then it's just ##\binom nk##, as both are 1. I think the convention is often to let ##\binom n{-1}=0##; then ##\binom{n+1}k=\binom nk+\binom n{k-1}## even when k=0.
  7. Sep 22, 2014 #6


    User Avatar
    Science Advisor
    Gold Member
    2017 Award

    You are right that the proof by induction approach can turn into a can of worms.
    Notice that [itex]
    \sum\limits_{k=0}^n {n \choose k}
    [/itex] is the total number of ways that any number of items (including 0 and n) can be selected from n items.

    If we indicate whether an item is selected or not by 1 or 0, respectively, and put the 1's and 0's in order, we can represent any set of selected items.

    For instance, starting with n=5 items, 10110 = select first, don't select second, select third, select fourth, don't select fifth, represents one way of selecting 3 of the 5. Now, how many zero/one patterns can we get from 5 binary digits?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook