Probability – Proof of Identity about Generalized Binomial Sequences

Question

I was going through this old question about a wealthy gambler:
Gambler with infinite bankroll reaching his target. The answer relies on the following identities from Concrete Mathematics by Graham, Knuth and Patashnik (equation numbers as they appear in the book).

$$B_2(z) = \sum\limits_{t=0}^\infty \frac{{2t+1\choose t}}{2t+1} z^t = \frac{1-\sqrt{1-4z}}{2z} \tag{5.68}$$

$$(B_2(z))^k = \left(\sum\limits_{t=0}^\infty {2t+1\choose t}\frac{1}{2t+1} z^t\right)^k = \sum\limits_{t=0}^\infty {2t+k \choose t} \frac{k}{2t+k}z^t \tag{5.70}$$

The expression on the far right of (5.70) is particularly interesting since it is the stopping time of a wealthy gambler targeting $k$.
It is also fascinating since $k$ seems to simply march into the infinite summation and replace $1$, somehow taking care of all the cross terms in the process.

I read through the chapter to see if I could find a proof for these identities (both of which I verified numerically).

Tracing my way back, I found the following (equivalent) definition of $B_u(z)$.

$$B_u(z) = \sum\limits_{t=0}^\infty \frac{ut \choose t}{(u-1)t+1} z^t \tag{5.58}$$

Then they simply state:

$$(B_u(z))^k = \sum\limits_{t=0}^\infty {ut+k \choose t} \frac{k}{ut+k} z^t \tag{5.60}$$

However, no proof is provided for these. So, I'm still scratching my head wondering how to prove (5.68) and (5.70).

---

My attempts:

For (5.70), we can say that in order for the gambler to reach $k$\$, he has to first reach $1$\$ and then repeat that feat $k$ times. This provides a rough sketch, but I'm still fascinated by the mechanical details (and (5.60) has no such interpretation in terms of gamblers).

For (5.68), I tried some of the approaches in the answers to this question.

First, Mathematica couldn't find a nice expression for the partial summation. So, @robojohn's approach probably won't work because if there were a function whose diff made up the terms of $B_2(z)$, the partial summation would have a nice expression in terms of that function.

Next, I tried @Marcus Scheuer's approach and got:

$$\frac{a_{t+1}}{a_t} = \frac{t+\frac 1 2}{t+2}(4z) = \frac{\frac{-1}{2}^\underline{t}}{-2^\underline{t}} (4z)$$

This doesn't work either since we don't get the $a+b=c+d$ condition required for the corollary he used and the $4z$ term interferes as well.

Answer 1

At first we show (5.68). Using the Binomial series expansion we obtain \begin{align*} \color{blue}{B_2(z)}&\color{blue}{=\frac{1-\sqrt{1-4z}}{2z}}\\ &=\frac{1}{2z}\left(1-\sum_{t=0}^\infty\binom{1/2}{t}(-4z)^t\right)\\ &=\frac{1}{2z}\sum_{t=1}^\infty\binom{1/2}{t}(-1)^{t+1}2^{2t}z^t\\ &=\sum_{t=1}^\infty\binom{1/2}{t}(-1)^{t+1}2^{2t-1}z^{t-1}\\ &=\sum_{t=0}^\infty\binom{1/2}{t+1}(-1)^t2^{2t+1}z^t\\ &\,\,\color{blue}{=\sum_{t=0}^\infty\binom{2t+1}{t}\frac{1}{2t+1}z^t}\tag{1} \end{align*} and the claim follows.

The last line (1) follows since we have \begin{align*} \binom{1/2}{t+1}&=\frac{1}{(t+1)!}\prod_{j=0}^t\left(\frac{1}{2}-j\right)=\frac{1}{(t+1)!}\cdot\frac{(-1)^{t+1}}{2^{t+1}}\prod_{j=0}^t(2j-1)\\ &=\frac{(-1)^t(2t-1)!!}{2^{t+1}(t+1)!}=\frac{(-1)^t(2t)!}{2^{t+1}(t+1)!(2t)!!}=\frac{(-1)^t(2t)!}{2^{2t+1}(t+1)!t!}\\ &=\frac{(-1)^t}{2^{2t+1}}\binom{2t+1}{t}\frac{1}{2t+1} \end{align*}

... and now the generalisation (5.70). In the following we use the coefficient of operator $[z^t]$ to denote the coefficient of $z^t$ in a series.

We observe the generating function $zB_2(z)=\frac{1}{2}\left(1-\sqrt{1-4z}\right)$ has the compositional inverse \begin{align*} \color{blue}{\left(z-z^2\right)^{\langle-1\rangle}=zB_2(z)}\tag{2} \end{align*} since \begin{align*} zB_2(z)-\left(zB_2(z)\right)^2&=\frac{1}{2}\left(1-\sqrt{1-4z}\right)-\frac{1}{4}\left(1-\sqrt{1-4z}\right)^2\\ &=\frac{1}{2}\left(1-\sqrt{1-4z}\right)-\frac{1}{4}\left(1-2\sqrt{1-4z}+1-4z\right)\\ &=z \end{align*}

The nice representation of the compositional inverse indicates we could apply the Lagrange Inversion Formula which gives us the coefficients of the $k$-th power of the generating function $zB_2(z)$.

Here we use it according to Theorem 5.4.2 in Enumerative Combinatorics, vol. 2 by R.P. Stanley.

Theorem: Let $F(z)=a_1z+a_2z^2+\cdots\in xK[[z]]$, where $a_1\ne 0$ (and $\mathrm{char} K=0$), and let $k,t\in \mathrm{Z}$. Then \begin{align*} t[z^t]F^{\langle-1\rangle}(z)^k=k[z^{t-k}]\left(\frac{z}{F(z)}\right)^t\tag{3} \end{align*}

Applying (3) with $F^{\langle -1\rangle}(z)=zB_2(z)$ we obtain \begin{align*} \color{blue}{[z^t]\left(zB_2(z)\right)^k}&=\frac{k}{t}[z^{t-k}]\left(\frac{z}{z-z^2}\right)^t\tag{4}\\ &=\frac{k}{t}[z^{t-k}]\frac{1}{\left(1-z\right)^t}\\ &=\frac{k}{t}[z^{t-k}]\sum_{j=0}^\infty\binom{-t}{j}(-z)^j\tag{5}\\ &=\frac{k}{t}[z^{t-k}]\sum_{j=0}^\infty\binom{t+j-1}{j}z^j\tag{6}\\ &=\frac{k}{t}\binom{2t-k-1}{t-1}\tag{7}\\ &\,\,\color{blue}{=\frac{k}{2t-k}\binom{2t-k}{t-k}}\tag{8} \end{align*}

Comment:

• In (4) we use $F^{\langle -1\rangle}(z)=zB_2(z)=\left(z-z^2\right)^{\langle -1\rangle}$ from (2).

• In (5) we apply the binomial series expansion.

• In (6) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^{q}$.

• In (7) we select the coefficient of $z^{t-k}$.

• In (8) we use the binomial identities $\binom{p}{q}=\frac{p}{q}\binom{p-1}{q-1}$ and $\binom{p}{q}=\binom{p}{p-q}$.

We finally obtain \begin{align*} \color{blue}{\left(zB_2(z)\right)^k}&=\left(\sum_{t=0}^\infty\binom{2t+1}{t}\frac{1}{2t+1}z^{t+1}\right)^k\tag{9}\\ &=\left(\sum_{t=1}^\infty\binom{2t-1}{t-1}\frac{1}{2t-1}z^t\right)^k\tag{10}\\ &=\sum_{t=k}^\infty\binom{2t-k}{t-k}\frac{k}{2t-k}z^t\tag{11}\\ &\,\,\color{blue}{=z^k\sum_{t=0}^\infty\binom{2t+k}{t}\frac{k}{2t+k}z^t}\tag{12} \end{align*} and the claim follows.

Comment:

• In (9) we use the identity (5.68) resp. (1).

• In (10) we shift the index $t$ by one to have an expansion in terms with factor $z^t$.

• In (11) we apply (8), the representation thanks to the Lagrange inversion formula.

• In (12) we shift the index to start with $t=0$.

Note that (12) can also be expressed as:

$$(zB_2(z))^k = z^k \sum\limits_{t=0}^\infty {2t+k-1 \choose t}\frac{k}{t+k}z^t$$