Xrfgtjtk

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) = sumlimits_{t=0}^infty frac{{2t+1choose t}}{2t+1} z^t = frac{1-sqrt{1-4z}}{2z} tag{5.68}$$

$$(B_2(z))^k = left(sumlimits_{t=0}^infty {2t+1choose t}frac{1}{2t+1} z^tright)^k = sumlimits_{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) = sumlimits_{t=0}^infty frac{ut choose t}{(u-1)t+1} z^t tag{5.58}$$

Then they simply state:

$$(B_u(z))^k = sumlimits_{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.

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}^inftybinom{1/2}{t}(-4z)^tright)\
&=frac{1}{2z}sum_{t=1}^inftybinom{1/2}{t}(-1)^{t+1}2^{2t}z^t\
&=sum_{t=1}^inftybinom{1/2}{t}(-1)^{t+1}2^{2t-1}z^{t-1}\
&=sum_{t=0}^inftybinom{1/2}{t+1}(-1)^t2^{2t+1}z^t\
&,,color{blue}{=sum_{t=0}^inftybinom{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}^tleft(frac{1}{2}-jright)=frac{1}{(t+1)!}cdotfrac{(-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^2right)^{langle-1rangle}=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-2sqrt{1-4z}+1-4zright)\
&=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+cdotsin xK[[z]]$, where $a_1ne 0$ (and $mathrm{char} K=0$), and let $k,tin mathrm{Z}$. Then
begin{align*}
t[z^t]F^{langle-1rangle}(z)^k=k[z^{t-k}]left(frac{z}{F(z)}right)^ttag{3}
end{align*}

Applying (3) with $F^{langle -1rangle}(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)^ttag{4}\
&=frac{k}{t}[z^{t-k}]frac{1}{left(1-zright)^t}\
&=frac{k}{t}[z^{t-k}]sum_{j=0}^inftybinom{-t}{j}(-z)^jtag{5}\
&=frac{k}{t}[z^{t-k}]sum_{j=0}^inftybinom{t+j-1}{j}z^jtag{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 -1rangle}(z)=zB_2(z)=left(z-z^2right)^{langle -1rangle}$ 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}^inftybinom{2t+1}{t}frac{1}{2t+1}z^{t+1}right)^ktag{9}\
&=left(sum_{t=1}^inftybinom{2t-1}{t-1}frac{1}{2t-1}z^tright)^ktag{10}\
&=sum_{t=k}^inftybinom{2t-k}{t-k}frac{k}{2t-k}z^ttag{11}\
&,,color{blue}{=z^ksum_{t=0}^inftybinom{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 sumlimits_{t=0}^infty {2t+k-1 choose t}frac{k}{t+k}z^t$$

Here is another approach I came across thanks to /u/whatkindofred on this reddit thread for proving (5.68). This approach starts from the LHS.

Let's suppose:

$$F(z) = sumlimits_{t=0}^infty a_t z_t = sumlimits_{t=0}^infty frac{2t choose t}{t+1} z^t$$

It is easy to see that:

$$(t+1)a_t = (4t-2)a_{t-1}tag{1.1}$$

Further suppose that:

$$G(z) = zF(z) = sumlimits_{t=0}^infty a_t z^{t+1}$$
So,
$$G'(z) = sumlimits_{t=0}^infty (t+1)a_t z^t$$

Using (1.1)
$$G'(z)= a_0 + sumlimits_{t=1}^infty(4t-2)a_{t-1}z^t$$

Since $a_0=1$,
$$G'(z) = 1+4 sumlimits_{t=1}^infty t a_{t-1} z^t - 2 sumlimits_{t=1}^infty a_{t-1}z_t$$
$$= 1+ 4 sum_{t=1}^infty (t+1)a_t z^{t+1} - 2 sumlimits_{t=1}^infty a_{t-1}z^t$$
$$G'(z)= 1+4zG'(z)-2G(z)tag{1.2}$$

But since $G(z)=zF(z)$,

$$G'(z)=F(z)+zF'(z)$$
Substituting into (1.2) we get:

$$F(z)+zF'(z)=1+2zF(z)+4z^2F'(z)$$
$$(4z^2-z)F'(z)+(2z-1)F(z)+1=0$$
$$F'(z) + g(z) F(z) = h(z) tag{1.3}$$

Where,
$$g(z) = frac{2z-1}{4z^2-z}$$
$$h(z)=frac{1}{z-4z^2}$$

Multiplying both sides of (1.3) by $e^{intlimits_{0}^x g(t)dt}$ we get,

$$e^{intlimits_{0}^z g(t)dt} F'(z) + e^{intlimits_{0}^x g(t)dt} g(z)F(z)=h(z)e^{intlimits_{0}^z g(t)dt}$$

$$=> frac{partial}{partial z}left(F(z)e^{intlimits_{0}^z g(t)dt}right) = h(z) e^{intlimits_{0}^z g(t)dt}$$

$$=> F(z)e^{intlimits_{0}^z g(t)dt} = intlimits_{y=0}^z h(y) e^{intlimits_{0}^y g(t)dt}tag{1.4}$$

Now, let's address the integrals.

$$int g(z)dz = -int frac{2z-1}{z-4z^2}$$

$$ = int frac{-2}{1-4z}dz + int frac{dz}{z(1-4z)}$$

$$=frac{log(1-4z)}{2} + int frac{4z+(1-4z)}{z(1-4z)}dz$$

$$=frac{log(1-4z)}{2}+ 4 int frac{dz}{1-4z}+int frac{dz}{z}$$

$$=frac{log(1-4z)}{2}- log(1-4z) +log(z)$$

$$=> int g(z) dz = logleft(frac{z}{sqrt{1-4z}}right)+b_1 $$

And so,

$$e^{int g(z)dz} = c_1frac{z}{sqrt{1-4z}}tag{1.5}$$

And this means,
$$int h(z) e^{int g(z)dz} = int frac{1}{z(1-4z)} c_2frac{z}{sqrt{1-4z}}dz$$

$$ = int c_2(1-4z)^{-frac 3 2}dz = frac{c_2}{sqrt{1-4z}}+c_3tag{1.6}$$

Substituting (1.5) and (1.6) into (1.4) yields:

$$F(z)=frac{d_1 + d_2 sqrt{1-4z}}{z}$$

But we know that $F(0)=1$ and for the above equation to not blow up at $z=0$ we must have $d_1=-d_2=d$ giving us,

$$F(z) = d left(frac{1-sqrt{1-4z}}{z}right)$$

And using $lim_{z to 0}F(z)=1$ we get $d=frac{1}{2}$ (use L' Hospitals rule) and the RHS of (5.68) follows.