# Why does this infinite series equal one?

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?

-
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 '14 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 '14 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 '14 at 22:01
Creative telescoping might be surprising sometimes :) – Jack D'Aurizio Jul 26 '14 at 22:09

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.

-
Very nice. Haven't seen this proof before. – marty cohen Jul 27 '14 at 1:17
Typo, I suppose. Shouldn't that be $\sum_{k=1}^{+\infty}$ instead of $\sum_{n=1}^{+\infty}$ ? – Han de Bruijn Jul 27 '14 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.

-
(+1) Very nice combinatorial argument. – Jack D'Aurizio Jul 27 '14 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 '14 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 '14 at 3:59
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 '14 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 '14 at 10:05

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

-