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

  • Thread starter nomadreid
  • Start date

nomadreid

Gold Member
1,254
81
(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:

nomadreid

Gold Member
1,254
81
:redface: oops, right. Thanks, Stephen Tashi, for spotting the typo. I have edited it.
So, back to the question......
 
1,757
123
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)
 

nomadreid

Gold Member
1,254
81
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.
 
21,960
3,264
(This is not HW, even though it may look a bit like it.)
And if it looks like homework, then it belongs in the homework forums! I'll move it for you :smile:
 

nomadreid

Gold Member
1,254
81
OK, thanks. Hope to get a response there. As a side note: the question arose as I was looking at Banach's matchbox problem.
 

nomadreid

Gold Member
1,254
81
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:
21,960
3,264
Or, to put it another way, why is the sum from k=0 to n of ([(n+k)Ck]/2k) equal to 2n?
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.
 
21,960
3,264
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.
Or is it

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

nomadreid

Gold Member
1,254
81
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.
 
21,960
3,264
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.
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?
 

nomadreid

Gold Member
1,254
81
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)
 

nomadreid

Gold Member
1,254
81
Thanks very much, micromass! That's a path I had not considered. Very elegant.:cool:
 
21,960
3,264
Thanks very much, micromass! That's a path I had not considered. Very elegant.:cool:
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.
 

nomadreid

Gold Member
1,254
81
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.
 
21,960
3,264
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.
 

nomadreid

Gold Member
1,254
81
Thanks, micromass. As you wrote, non-trivial, but it gives me some new techniques to get acquainted with.
 
21,960
3,264
The first one, I can't find at the moment.
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,960
3,264
Well, this works, but an elementary approach still eludes me.
 

Want to reply to this thread?

"Combinatorics: 1= ((n+k)Cr)*((1/2)^(n+k)) from k = 0 to n" You must log in or register to reply here.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Top Threads

Top