1
$\begingroup$

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.

$\endgroup$
3
+50
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ @RohitPandey: You're welcome. I'm thinking about the other identity. But in fact I can start working on it not before tomorrow evening. Maybe some other can post an answer earlier than me. $\endgroup$ – Markus Scheuer Jan 6 at 23:44
  • 1
    $\begingroup$ Sure, no hurry. Much appreciated. $\endgroup$ – Rohit Pandey Jan 6 at 23:46
  • 1
    $\begingroup$ @RohitPandey: I've added a proof of (5.70). Regards, $\endgroup$ – Markus Scheuer Jan 9 at 23:18
  • 1
    $\begingroup$ Thanks, will take me some time to digest this. Appreciate the exposure to these beautiful techniques. Wish I could upvote multiple times :) $\endgroup$ – Rohit Pandey Jan 10 at 1:53
  • 1
    $\begingroup$ @RohitPandey: Many thanks for granting a bounty. This is extraordinarily kind of you. Currently I'm busy, but soon I will give you some references, which might help you to dig somewhat deeper into the concepts of the Lagrange inversion formula. $\endgroup$ – Markus Scheuer Jan 11 at 7:36
1
$\begingroup$

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) = \sum\limits_{t=0}^\infty a_t z_t = \sum\limits_{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) = \sum\limits_{t=0}^\infty a_t z^{t+1}$$ So, $$G'(z) = \sum\limits_{t=0}^\infty (t+1)a_t z^t$$

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

Since $a_0=1$, $$G'(z) = 1+4 \sum\limits_{t=1}^\infty t a_{t-1} z^t - 2 \sum\limits_{t=1}^\infty a_{t-1}z_t$$ $$= 1+ 4 \sum_{t=1}^\infty (t+1)a_t z^{t+1} - 2 \sum\limits_{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^{\int\limits_{0}^x g(t)dt}$ we get,

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

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

$$=> F(z)e^{\int\limits_{0}^z g(t)dt} = \int\limits_{y=0}^z h(y) e^{\int\limits_{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 = \log\left(\frac{z}{\sqrt{1-4z}}\right)+b_1 $$

And so,

$$e^{\int g(z)dz} = c_1\frac{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_2\frac{z}{\sqrt{1-4z}}dz$$

$$ = \int c_2(1-4z)^{-\frac 3 2}dz = \frac{c_2}{\sqrt{1-4z}}+c_3\tag{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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.