# How to calculate the sum of the following series?

I would like to find the sum of the following series:

$$\sum_{n=0}^{\infty} \binom{2n+1}{n+1} (p(1-p))^n$$

where $$0. I put it on Wolfram and it said that this series converges to $$\frac{\sqrt{(2p-1)^2}-1}{2p(p-1)\sqrt{(2p-1)^2}}$$

I initially thought it was a Geometric progression, but turns out its not.

I am guessing it could work with binomial series, where we have $$\sum_{k=0}^{\infty}\binom{\alpha}{k}x^k=(1+x)^{\alpha}$$. But here, my $$\alpha$$ depends on $$k$$, so I'm slightly stuck. I am aware that finding the sum of a series is hard and am unsure of how else to go about finding the sum of this series. Any help would be appreciated!

• Jul 12, 2021 at 10:13
• @lab bhattacharjee None of the methods mentioned there seem to work put here, except for the Catalan numbers one, which I haven't really learn about. Jul 12, 2021 at 10:34
• So, it doesn't help solving the question, but as a simplification (to remove extra unnecessary symbols), maybe set $x=p(1-p)$, and look at the sum $\sum_{n=0}^\infty \binom{2n+1}{n+1} x^n$ for $|x|<1/4$. Jul 12, 2021 at 10:41
• Hint: $\sum_{n=0}^\infty {2n+1 \choose n+1} x^n = \sum_{n=0}^\infty {2n \choose n}x^n \frac{2n+1}{n+1} = \sum_{n=0}^\infty {2n \choose n}(2 - \frac{1}{n+1})x^n = 2\sum_{n=0}^\infty {2n \choose n}x^n - \sum_{n=0}^\infty {2n \choose n} \frac{x^n}{n+1}$. For the first one see the link by lab bhattarchajee. For the second one, try integrating the first one. Jul 12, 2021 at 10:47
• @DominikKutek Makes sense, thank you so much!! Jul 12, 2021 at 11:16

The series representation \begin{align*} \color{blue}{\sum_{n=0}^{\infty}\binom{2n+1}{n+1}\left(p(1-p)\right)^n}\tag{1} \end{align*} is nice and instructive.

WA: We start with the result provided by Wolfram Alpha. We obtain for $$0 \begin{align*} \color{blue}{\frac{\sqrt{(2p-1)^2}-1}{2p(p-1)\sqrt{(2p-1)^2}}} &=\frac{1-|2p-1|}{2p(1-p)|2p-1|}\\ &=\frac{1-(1-2p)}{2p(1-p)(1-2p)}\\ &=\frac{1}{(1-p)(1-2p)}\\ &=\frac{1}{p}\left(\frac{1}{1-2p}-\frac{1}{1-p}\right)\\ &=\frac{1}{p}\left(\sum_{j=0}^{\infty}\left(2p\right)^j-\sum_{j=0}^{\infty}p^j\right)\\ &=\frac{1}{p}\sum_{j=1}^{\infty}\left(2^j-1\right)p^j\\ &\,\,\color{blue}{=\sum_{j=0}^\infty\left(2^{j+1}-1\right)p^j}\tag{2}\\ &=1+3p+7p^2+15p^3+63p^4+\cdots \end{align*}

So, according to WA we see that a series expansion of (1) at $$p=0$$ gives the nice and simple difference of geometric series in (2).

But of course, this has to be shown. We use the coefficient of operator $$[p^t]$$ to denote the coefficient of $$p^t$$ of a series.

Coefficient extraction:

We obtain from (1) \begin{align*} \color{blue}{[p^t]}&\color{blue}{\sum_{n=0}^{\infty}\binom{2n+1}{n+1}\left(p(1-p)\right)^n}\\ &=\sum_{n=0}^t\binom{2n+1}{n+1}[p^t]\left(p(1-p)\right)^n\tag{3.1}\\ &=\sum_{n=0}^t\binom{2n+1}{n+1}[p^{t-n}](1-p)^n\tag{3.2}\\ &\,\,\color{blue}{=\sum_{n=0}^t\binom{2n+1}{n+1}\binom{n}{t-n}(-1)^{t-n}}\tag{3.3} \end{align*}

Comment:

• In (3.1) we use the linearity of the coefficient of operator and set the upper limit of the series to $$t$$ since other values of $$n$$ do not contribute to the coefficient of $$p^t$$.

• In (3.2) we use the identity $$[p^{t-n}]A(p)=[p^t]p^nA(p)$$.

• In (3.3) we select the coefficient of $$p^{t-n}$$.

Binomial identity:

Since the coefficient of $$p^t$$ in (2) is according to WA equal to (3.3) we have finally to show the nice binomial identity: \begin{align*} \color{blue}{\sum_{n=0}^t\binom{2n+1}{n+1}\binom{n}{t-n}(-1)^{t-n}=2^{t+1}-1\qquad\qquad t\geq 0}\tag{4} \end{align*}

We obtain \begin{align*} \color{blue}{\sum_{n=0}^t}&\color{blue}{\binom{2n+1}{n+1}\binom{n}{t-n}(-1)^{t-n}}\\ &=\sum_{n=0}^t\binom{t+1}{n+1}\binom{2n+1}{t+1}(-1)^{t-n}\tag{4.1}\\ &=\sum_{n=1}^{t+1}\binom{t+1}{n}\binom{2n-1}{t+1}(-1)^{t+1-n}\tag{4.2}\\ &=\sum_{n=1}^{t+1}\binom{t+1}{n}[z^{t+1}](1+z)^{2n-1}(-1)^{t+1-n}\tag{4.3}\\ &=(-1)^{t+1}[z^{t+1}](1+z)^{-1}\sum_{n=1}^{t+1}\binom{t+1}{n}\left(-(1+z)^2\right)^n\tag{4.4}\\ &=(-1)^{t+1}[z^{t+1}](1+z)^{-1}\left(\left(1-(1+z)^2\right)^{t+1}-1\right)\tag{4.5}\\ &=(-1)^{t+1}[z^{t+1}](1+z)^{-1}\left(\left((-2z-z^2\right)^{t+1}-1\right)\\ &=[z^0](1+z)^{-1}(2+z)^{t+1}-(-1)^{t+1}[z^{t+1}](1+z)^{-1}\\ &=[z^0]\sum_{j=0}^{t+1}\binom{t+1}{j}2^jz^{t+1-j}(1+z)^{-1}-1\tag{4.6}\\ &\,\,\color{blue}{=2^{t+1}-1}\tag{4.7} \end{align*} and the claim follows.

Comment:

• In (4.1) we use the binomial identity $$\binom{2n+1}{n+1}\binom{n}{t-n}=\binom{t+1}{n+1}\binom{2n+1}{t+1}$$.

• In (4.2) we shift the index to start with $$n=1$$.

• In (4.3) we use the representation $$[z^t](1+z)^n=\binom{n}{t}$$.

• In (4.4) we factor out terms which do not depend on $$n$$.

• In (4.5) we apply the binomial theorem.

• In (4.6) we use $$[z^{t+1}](1+z)^{-1}=[z^{t+1}]\left(1-z+z^2-z^3+\cdots\right)=(-1)^{t+1}$$ and we also apply the binomial theorem.

• In (4.7) we observe that only $$j=t+1$$ contributes to the coefficient of $$z^0$$.

• Oh my god!! This makes a lot of sense. Thank you so much for such an elaborate explanation! Jul 13, 2021 at 4:49
• @Batrachotoxin: You're welcome! Many thanks for your nice comment. :-) Jul 13, 2021 at 6:15
• Thanks @MarkusScheuer for working on this question which I did not see initially. (+1). I have posted a complex variable proof of the binomial identity. Jul 13, 2021 at 22:03

Here is an alternate proof of the binomial identity by Markus Scheuer. We seek to show that

$$\sum_{q=0}^n {q\choose n-q} (-1)^{n-q} {2q+1\choose q+1} = 2^{n+1}-1.$$

The LHS is

$$\frac{(-1)^n}{2\pi i} \int_{|z|=\varepsilon} \frac{1}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\gamma} \sum_{q=0}^n (-1)^q z^q (1+z)^q \frac{(1+w)^{2q+1}}{w^{q+2}} \; dw \; dz.$$

There is no contribution when $$q\gt n$$ and we may extend $$q$$ to infinity:

$$\frac{(-1)^n}{2\pi i} \int_{|z|=\varepsilon} \frac{1}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1+w}{w^2} \frac{1}{1+z(1+z)(1+w)^2/w} \; dw \; dz \\ = \frac{(-1)^n}{2\pi i} \int_{|z|=\varepsilon} \frac{1}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1+w}{w} \frac{1}{(1+z+wz)(z+(1+z)w)} \; dw \; dz.$$

Now we determine $$\varepsilon$$ and $$\gamma$$ so that the geometric series converges and the pole at $$w=-z/(1+z)$$ is inside $$|w|=\gamma$$ while the pole at $$w=-(1+z)/z$$ is not. For the series we require $$|z(1+z)(1+w)^2/w| \lt 1.$$ With $$|z(1+z)| \le \varepsilon (1+\varepsilon)$$ and $$|w/(1+w)^2| \ge \gamma/(1+\gamma)^2$$ we need $$\varepsilon(1+\varepsilon) \lt \gamma/(1+\gamma)^2.$$ Observe that on $$[0,1]$$ we have $$\gamma/(1+\gamma)^2 \ge \gamma/4$$ since $$4\ge (1+\gamma)^2.$$ For $$\gamma/4 \gt \varepsilon(1+\varepsilon)$$ we choose $$\gamma=8\varepsilon$$ with $$\varepsilon \ll 1$$ and we have our pair. Now for the pole at $$-z/(1+z)$$ we need for the maximum norm $$\varepsilon/(1-\varepsilon) \lt \gamma = 8\varepsilon$$ which holds with $$\varepsilon \lt 7/8$$ which we will enforce. The second pole under consideration is $$-(1+z)/z = -1 - 1/z.$$ The closest this comes to the origin is $$-1+\varepsilon = -1 + \gamma/8.$$ To see that this is outside $$|w|=\gamma$$ we need $$-1+\gamma/8 \lt -\gamma$$ or $$\gamma\lt 8/9.$$ This means we instantiate $$\varepsilon$$ to $$\varepsilon \lt 1/9$$, which completes the discussion of the contour.

Now residues sum to zero and the residue at infinity in $$w$$ is zero by inspection which means that the inner integral is minus the residue at $$w= -(1+z)/z$$, as it is equal to the sum of the residues at zero and at $$w=-z/(1+z)$$. We write

$$- \frac{1}{z} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1+w}{w} \frac{1}{((1+z)/z+w)(z+(1+z)w)} \; dw.$$

We get from this being a simple pole the contribution (here $$(1+w)/w = 1/(1+z)$$)

$$- \frac{1}{z} \frac{1}{1+z} \frac{1}{z-(1+z)^2/z} = \frac{1}{1+z} \frac{1}{1+2z}$$

which combined with the integral in $$z$$ gives

$$(-1)^n [z^n] \frac{1}{1+z} \frac{1}{1+2z} = (-1)^n \sum_{q=0}^n (-1)^q 2^q (-1)^{n-q} = \sum_{q=0}^n 2^q.$$

This is indeed

$$\bbox[5px,border:2px solid #00A000]{ 2^{n+1}-1}$$

as claimed.

• Great derivation! I appreciate the helpful discussion of the contour. Many thanks for this contribution. (+1) Jul 14, 2021 at 6:41

Let your sum be $$s(p)$$.

Consider a random walk starting at 0 and moving right with probability $$p$$ and left with probability $$1-p$$. Then $$ps(p)$$ is the expected time the walk spends at $$1$$.

If you never reach $$1$$ then the time at $$1$$ is zero. Thus you need to reach $$1$$, the probability of which is $$\frac{p}{(1-p)}$$ (see Theorem 1, page 4). Then after that, the walk "restarts" and the expected time spent at $$1$$ is the same as the expected time spent at $$0$$ for the original walk. This expected time spent is $$\frac{1}{(1-2p)}$$ : the probability of ever returning to $$0$$ is $$2p$$ (see Theorem 3, page 5), so the expected time spent at $$0$$ is $$1+(2p)+(2p)^2+...=\frac{1}{1-2p}$$ (Problem 3, page 6).

In summary, the expected time at $$1$$ is $$\frac{p}{(1-p)(1-2p)}$$ and $$s(p)=\frac{1}{(1-p)(1-2p)}$$