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

1. Apr 6, 2014

(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. Apr 6, 2014

### Stephen Tashi

3. Apr 6, 2014

oops, right. Thanks, Stephen Tashi, for spotting the typo. I have edited it.
So, back to the question......

4. Apr 6, 2014

### homeomorphic

Not sure you've stated it correctly, still. Is this what you wanted?

$1 = 1^n = (\frac{1}{2} + \frac{1}{2} )^n$

$= \Sigma_{k = 0}^n {{n}\choose{k}} \frac{1}{2^n}$ (binomial expansion)

5. Apr 6, 2014

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.

6. Apr 6, 2014

### micromass

And if it looks like homework, then it belongs in the homework forums! I'll move it for you

7. Apr 6, 2014

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

8. Apr 7, 2014

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
9. Apr 7, 2014

### micromass

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

$$\sum_{k=0}^n \binom{n+k}{k} \frac{1}{2^k} = 2^n$$

because the OP and the title both say completely different things.

10. Apr 7, 2014

### micromass

Or is it

$$\sum_{k=0}^n \binom{n+k}{n} \frac{1}{2^k} = 2^n$$

11. Apr 7, 2014

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.

12. Apr 7, 2014

### micromass

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?

13. Apr 7, 2014

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)

14. Apr 7, 2014

Thanks very much, micromass! That's a path I had not considered. Very elegant.

15. Apr 7, 2014

### micromass

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

$$\frac{y^n}{(1-y)^{n+1}} = \sum_{k=n}^{+\infty} \binom{k}{n} x^k$$

But then you also need some formula for

$$\sum_{k=2n}^{+\infty} \binom{k}{n}x^k$$

which I haven't found yet.

16. Apr 7, 2014

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.

17. Apr 7, 2014

### micromass

OK, a highly nontrivial way is this:

We are interested in

$$x_a = \sum_{k=a}^{+\infty} \binom{k}{n} \frac{1}{2^k}$$

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

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

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

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

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.

18. Apr 7, 2014

Thanks, micromass. As you wrote, non-trivial, but it gives me some new techniques to get acquainted with.

19. Apr 7, 2014

### micromass

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

$$\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))$$

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

20. Apr 7, 2014

### micromass

Well, this works, but an elementary approach still eludes me.