Proof of identity about generalized binomial sequences.
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.
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$$
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.