How to calculate the sum of the following series?

Question

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<p<\frac{1}{2}$. 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!

Answer 1

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<p<\frac{1}{2}$ \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$.

Answer 2

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.

Answer 3

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)}$