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: 1= ((n+k)Cr)*((1/2)^(n+k)) from k = 0 to n

  1. Apr 6, 2014 #1

    nomadreid

    User Avatar
    Gold Member

    (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

    nomadreid

    User Avatar
    Gold Member

    :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

    nomadreid

    User Avatar
    Gold Member

    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
    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

    nomadreid

    User Avatar
    Gold Member

    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

    nomadreid

    User Avatar
    Gold Member

    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
    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
    Or is it

    [tex]\sum_{k=0}^n \binom{n+k}{n} \frac{1}{2^k} = 2^n [/tex]
     
  12. Apr 7, 2014 #11

    nomadreid

    User Avatar
    Gold Member

    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
    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

    nomadreid

    User Avatar
    Gold Member

    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

    nomadreid

    User Avatar
    Gold Member

    Thanks very much, micromass! That's a path I had not considered. Very elegant.:cool:
     
  16. Apr 7, 2014 #15
    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

    nomadreid

    User Avatar
    Gold Member

    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
    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

    nomadreid

    User Avatar
    Gold Member

    Thanks, micromass. As you wrote, non-trivial, but it gives me some new techniques to get acquainted with.
     
  20. Apr 7, 2014 #19
    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
    Well, this works, but an elementary approach still eludes me.
     
  22. Apr 7, 2014 #21

    nomadreid

    User Avatar
    Gold Member

  23. Apr 7, 2014 #22
    OK, but that solves it right? I don't get why you say "special case"? I'll write it here for future reference:

    You need to find

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

    Multiply by ##4^n/4^n## to get

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

    Apply the relation ##2^a = \sum_{j=0}^a \binom{a}{j}## to get

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

    Switching around the sums and allowing the convention that if ##\binom{a}{b}=0## if ##b>a##, we get

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

    the relation in Knuth is

    [tex]\sum_{k=0}^l \binom{l-k}{m}\binom{q+k}{n} = \binom{l+q+1}{m+n+1}[/tex]

    Thus we get

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

    Change variables ##l=j+n+1##:

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

    Applying that ##\binom{2n+1}{l} = \binom{2n+1}{2n+1-l}##, we see that

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

    Again applying ##2^a = \sum_{j=0}^a \binom{a}{j}##, we see that this is equal to

    [tex]\frac{1}{2^{2n+1}}2^{2n+1} = 1[/tex]
     
    Last edited: Apr 7, 2014
  24. Apr 7, 2014 #23

    nomadreid

    User Avatar
    Gold Member

    Thanks again, micromass. Yes, the phrase "a special case" was misplaced; I was being overly careful before I had seen the reference in Knuth et al. (I have in fact not yet obtained a copy, so I still need to look at it.) Apparently, as you say, this now solves it, and your exposition is nice and clear -- except that I think you left something out in the line
    "Applying that ##\binom{2n+1}{l} = \binom{2n+1}{l}##, we see that..."
     
    Last edited: Apr 7, 2014
  25. Apr 7, 2014 #24
    Thank you, that was a typo. Well, all that remains is proving the relation in Knuth, which is not done there. I think an induction proof works, but I don't like that. Consider the function

    [tex]f_n(x) = \frac{x^n}{(1-x)^{n+1}}[/tex]

    We know the binomial series

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

    Thus

    [tex]f_n(x) = \sum_{k=0}^{+\infty} \binom{k}{n} x^k[/tex]

    with the usual convention that ##\binom{k}{n} = 0## if ##n>k##

    Thus ##xf_n(x)f_m(x) = f_{n+m+1}(x)##. By the Cauchy product of series, we then see that

    [tex]\sum_{k=-1}^{+\infty} \binom{k+1}{n+m+1} x^k = \sum_{k=0}^{+\infty} x^k \sum_{j=0}^k \binom{j}{n}\binom{k-j}{m}[/tex]

    Thus we see the identity (with additionally substituting ##t=k##

    [tex]\sum_{j=0}^k \binom{j}{n}\binom{t-j}{m} = \binom{t+1}{n+m+1}[/tex]

    Substituting ##j=l-k##, we get

    [tex]\sum_{k=0}^{l-k} \binom{l-k}{n}\binom{t-l+k}{m} = \binom{t+1}{n+m+1}[/tex]

    The result now follows after substiting ##q=t-l##.
     
  26. Apr 7, 2014 #25

    nomadreid

    User Avatar
    Gold Member

    Excellent! Thanks so very much. Yes, I finally got hold of Knuth and was surprised not to find a derivation for the the principle in question. So your explanation definitely fills a gap, completing the answer to my question. I am very grateful.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted