How to compute $\sum_{k=0}^\infty {2k \choose k} p^k (1-p)^k$

Question

Trying to compute $$\sum_{k=0}^\infty {2k \choose k} p^k (1-p)^k$$ for $0 < p < 1$.

All I have been able to do so far is using the ratio test and Stirling's approximation to show that this sum is infinite iff $p=0.5$.

Answer 1

Hint: Consider the Taylor expansion of $\frac{1}{\sqrt{1+x}}$.

Answer: It's straightforward to see that the Taylor series is $$\sum_{k=0}^{\infty}{\binom{2k}{k}\left(-\frac{x}{4}\right)^k},$$ which is valid in $(-1,1)$, plugging in $x=4p(p-1)$ (note that this won't work for $p=\frac{1}{2}$) gives the sum is: $$\frac{1}{\sqrt{1-4p(1-p)}}=\frac{1}{|1-2p|}.$$

Answer 2

Wlog suppose $p>1/2$.

Note that the sum is the expected number of visits to $0$ of the random walk with probability $p$ of moving left (starting from $0$). If the position of the random walk at time $n$ is $x_n$, then $\left(\frac{1-p}{p}\right)^{x_n}$ is a martingale.

It follows that starting from $1$, the probability of reaching $0$ before $t$ tends to $\frac{1-p}{p}$ as $t\to\infty$ (by the optional stopping theorem), so the probability of returning to $0$ from $1$ is $\frac{1-p}{p}$. The probability of returning to $0$ from $-1$ is $1$, and so the probability of returning to $0$ is $p\cdot\frac{1-p}{p}+(1-p)\cdot 1=2(1-p)$.

The expected number of visits to $0$ is therefore $1+2(1-p)+(2(1-p))^2+\cdots=\frac{1}{2p-1}$.