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!

Combinatorics: 1= ((n+k)Cr)*((1/2)^(n+k)) from k = 0 to n

  1. Apr 6, 2014 #1
    (This is not HW, even though it may look a bit like it.)
    Using the notation nCr in the combinatorics meaning,
    The sum of ((n+k)Cn)*((1/2)^(n+k)) from k = 0 to n equals one. Why?
    (I thought it might use the identity (n+1)Cr = nCr+nC(r-1), but that didn't get me anywhere.)
    Thanks in advance for any pointers.
     
    Last edited: Apr 6, 2014
  2. jcsd
  3. Apr 6, 2014 #2

    Stephen Tashi

    User Avatar
    Science Advisor

  4. Apr 6, 2014 #3
    :redface: oops, right. Thanks, Stephen Tashi, for spotting the typo. I have edited it.
    So, back to the question......
     
  5. Apr 6, 2014 #4
    Not sure you've stated it correctly, still. Is this what you wanted?

    [itex]1 = 1^n = (\frac{1}{2} + \frac{1}{2} )^n [/itex]

    [itex]= \Sigma_{k = 0}^n {{n}\choose{k}} \frac{1}{2^n}[/itex] (binomial expansion)
     
  6. Apr 6, 2014 #5
    Thanks, homeomorphic, but no: my title stated it incorrectly (I forgot to edit the title, and now it no longer gives me that option), but I have edited the original question, as Stephen Tashi pointed out. The binomial expansion you suggest only gives me
    Sum of (nCk)*((1/2)^(k)) from k = 0 to n
    Note the differences to
    Sum of ((n+k)Cn)*((1/2)^(n+k)) from k = 0 to n
    As a random example, I asked Wolfram Alpha to compute this, with n=7, and it was indeed one. This is not a proof, but a reassurance that I wrote it right.
     
  7. Apr 6, 2014 #6

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    And if it looks like homework, then it belongs in the homework forums! I'll move it for you :smile:
     
  8. Apr 6, 2014 #7
    OK, thanks. Hope to get a response there. As a side note: the question arose as I was looking at Banach's matchbox problem.
     
  9. Apr 7, 2014 #8
    reformulated:sum from k=0 to n of (n+k)Ck = 2^n

    Or, to put it another way, why is the sum from k=0 to n of ([(n+k)Ck]/2k) equal to 2n?
     
    Last edited: Apr 7, 2014
  10. Apr 7, 2014 #9

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    I'm confused what the problem actually is. Is this the problem:

    [tex]\sum_{k=0}^n \binom{n+k}{k} \frac{1}{2^k} = 2^n[/tex]

    because the OP and the title both say completely different things.
     
  11. Apr 7, 2014 #10

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Or is it

    [tex]\sum_{k=0}^n \binom{n+k}{n} \frac{1}{2^k} = 2^n [/tex]
     
  12. Apr 7, 2014 #11
    They are the same thing, since (n+k)Ck = (n+k)C[(n+k)-n]=(n+k)Cn.
    I merely restated it in the two fashions, because perhaps one formulation is easier to prove than the other.
     
  13. Apr 7, 2014 #12

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Oh right, haha. Shame on me for missing that... I'm gonna think about this for a while. I assume you have already tried induction?
     
  14. Apr 7, 2014 #13
    Thanks for considering it, micromass. Of course I tried induction, but got stuck. This does not mean that induction is not the right way to go; it could very well just mean that I am missing an obvious step in the induction. In the induction step I get
    Assume
    sum from k=0 to n of ([(n+k)C(k)]/2k) = 2n
    Prove
    sum from k=0 to n+1 of ([(n+k+1)C(k)]/2k) = 2n+1
    Then
    sum from k=0 to n+1 of ([(n+k+1)C(k)]/2k) = [sum from k=0 to n of ([(n+k+1)Ck]/2k)]+[(2n+1)C(n+1)/2n+1] and then?
    (similarly with the other formulation)
     
  15. Apr 7, 2014 #14
    Thanks very much, micromass! That's a path I had not considered. Very elegant.:cool:
     
  16. Apr 7, 2014 #15

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Yeah, it's also not entirely correct. You need to do something with the Taylor series

    [tex]\frac{y^n}{(1-y)^{n+1}} = \sum_{k=n}^{+\infty} \binom{k}{n} x^k[/tex]

    But then you also need some formula for

    [tex]\sum_{k=2n}^{+\infty} \binom{k}{n}x^k[/tex]

    which I haven't found yet.
     
  17. Apr 7, 2014 #16
    Thanks again, micromass; at least for the moment it gives me another line of thought to pursue. Although this is in the "HW & HW-similar" section, it is not HW and so there is no "due date", so if you come up with something anytime in the future, I would be grateful to hear about it.
     
  18. Apr 7, 2014 #17

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    OK, a highly nontrivial way is this:

    We are interested in

    [tex]x_a = \sum_{k=a}^{+\infty} \binom{k}{n} \frac{1}{2^k}[/tex]

    If we found this, then your sum is simply ##x_{n} - x_{2n+1}##. Now, it is easily seen that

    [tex]x_a = \binom{a}{n} \frac{1}{2^a} {}_2F_1(1,a+1;a-n+1;1/2)[/tex]

    Where ##{}_2F_1## is the hypergeometric function (it's really easy to see, it just follows from the definition, I might have made some computation errors tho). So we want to calculate

    [tex]{}_2F_1(1,n+1;1;1/2)~\text{and}~{}_2F_1(1,2n+2;n+3;1/2)[/tex]

    The former can be calculated by applying a Euler transformation and yields ##2^{n+1}##: http://en.wikipedia.org/wiki/Hypergeometric_function#Fractional_linear_transformations

    The first one, I can't find at the moment.
     
  19. Apr 7, 2014 #18
    Thanks, micromass. As you wrote, non-trivial, but it gives me some new techniques to get acquainted with.
     
  20. Apr 7, 2014 #19

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    The second one [tex]{}_2F_1(1,2n+2;n+3;1/2)[/tex] can be calculated by applying Gauss' contiguous relations. Specifically, I'm applying

    [tex]\frac{(c-a){}_2F_1(a-1,b;c;z) + (a -c + bz){}_2F_1(a,b;c;z)}{1-z} = (c-1)({}_2F_1(a,b;c-1;z) - {}_2F_1(a,b;c;z))[/tex]

    This means that we simply need to find ##{}_2F_1(0,2n+2;n+3;1/2)## which is easily done by applying the definition. We also need to find ##{}_2F_1(1,2n+2;n+2;1/2)##. But this can be done by Gauss' second summation theorem: http://en.wikipedia.org/wiki/Hypergeometric_function#Values_at_z.C2.A0.3D.C2.A01.2F2
     
  21. Apr 7, 2014 #20

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Well, this works, but an elementary approach still eludes me.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Combinatorics: 1= ((n+k)Cr)*((1/2)^(n+k)) from k = 0 to n
  1. K|n!+k from k=2,3,4 .n (Replies: 10)

Loading...