Why does this infinite series equal one? $\sum_{k=1}^\infty \binom{2k}{k} \frac{1}{4^k(k+1)}=1$

Solution 1:

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.

Solution 2:

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.