Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Why does

$$\sum_{k=1}^\infty \binom{2k}{k} \frac{1}{4^k(k+1)}=1$$

Is there an intuitive method by which to derive this equality?

share|improve this question
1  
One explanation which would be quite intuitive (if one could find it) would be to interpret each term as the probability of some event. Then adding the terms up to get 1 would make simply mean that there's a certainty of something happening. (But I'll admit, I don't see such an interpretation off the top of my head.) –  Semiclassical Jul 26 at 21:56
    
@Semiclassical Given the appereance of $\binom{2k}k$ and $2^{2k}$, I would urge you to think about picking certain subsets of $[2k]$! (I haven't thought about it, though) –  Pedro Tamaroff Jul 26 at 21:59
    
@PedroTamaroff: I was thinking something like: flip coins with certain odds until you've got as many heads up as heads down. Either that or something relating to these being the catalan numbers $\times 4^{-k}.$ –  Semiclassical Jul 26 at 22:01
    
Creative telescoping might be surprising sometimes :) –  Jack D'Aurizio Jul 26 at 22:09

3 Answers 3

Your series is a telescoping one, since: $$\begin{eqnarray*}\frac{1}{4^{k+1}}\binom{2k+2}{k+1}-\frac{1}{4^k}\binom{2k}{k}&=&\frac{1}{4^{k+1}}\binom{2k}{k}\left(\frac{(2k+2)(2k+1)}{(k+1)^2}-4\right)\\&=&-\frac{1}{2(k+1)4^{k}}\binom{2k}{k},\end{eqnarray*}$$ hence: $$\sum_{k=1}^{+\infty}\binom{2k}{k}\frac{1}{4^k(k+1)}=2\sum_{k=1}^{+\infty}\left(\frac{1}{4^k}\binom{2k}{k}-\frac{1}{4^{k+1}}\binom{2k+2}{k+1}\right)=\frac{2}{4}\binom{2}{1}=1.$$ No need of generating functions or integrals.

share|improve this answer
    
Very nice. Haven't seen this proof before. –  marty cohen Jul 27 at 1:17
1  
Typo, I suppose. Shouldn't that be $\sum_{k=1}^{+\infty}$ instead of $\sum_{n=1}^{+\infty}$ ? –  Han de Bruijn Jul 27 at 10:41

Here's a counting proof. Suppose I play the following game: I flip a coin once; assume w/o loss of generality that it's heads. I then continue flipping that coin until exactly as many tails have come up as heads. What is the probability $P(k)$ that a total of $k$ heads and $k$ tails will have been seen?

First, note that a given sequence of $2k$ coin flips has a probability of $2^{-2k}$ of occuring. However, not all sequences of coin flips are allowed: only those where the number of heads is always at least as much as the number of tails. (So $HTHHTT$ is fine but not $HTTTHH$). Hence it may not be obvious how to count this.

Luckily this counting problem is well-known, and the number of allowed outcomes of length $2k$ is the $k$th Catalan number $C_k=\dbinom{2k}{k}\dfrac{1}{k+1}.$ (See the Wikipedia article for details.) Consequently the probability of $k$ heads and $k$ tails occuring is $P_k=C_k\,2^{-2k}$.

With that in mind, what is the probability of any outcome occuring? It must of course be a certainty, so we conclude that $$ \sum_{k=1}^\infty P_k =\sum_{k=1}^\infty \binom{2k}{k} \frac{2^{-2k}}{k+1}=1$$ which is exactly the identity desired.

share|improve this answer
    
(+1) Very nice combinatorial argument. –  Jack D'Aurizio Jul 27 at 1:12
    
@JackD'Aurizio: Thanks! I debated whether or not to include a derivation of $C_n$ as well but decided it wasn't crucial for explaining the intuition. –  Semiclassical Jul 27 at 1:17
    
You still need to show that the probability of never seeing the same number of heads and tails is 0. –  JimmyK4542 Jul 27 at 3:59
1  
For a rigorous explanation, sure. But the poster asked for intuition, and that point seems sufficiently technical as to not be necessary. @JimmyK4542 –  Semiclassical Jul 27 at 4:06
    
Since you've invoked a theorem for the Catalan number formula, you could invoke a theorem about random walks in place of "it must of course be a certainty" :-) The notion of the coin-tosses continuing forever is precisely the notion of no outcome occurring. –  Steve Jessop Jul 27 at 10:05

The generating function of $x_n=\dfrac{1}{n+1}\displaystyle\binom{2n}n$ is $$\frac{1-\sqrt{1-4x}}{2x}$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.