About the identity $\sum\limits_{i=0}^{\infty}\binom{2i+j}{i}z^i=\frac{B_2(z)^j}{\sqrt{1-4z}}$ In the paper A Probabilistic Algorithm for k-SAT Based on Limited Local Search and Restart, by Uwe Schöning, I fail to understand an identity used in a proof:
$$\sum_{i=0}^{\infty}\binom{2i+j}{i}z^i=\frac{B_2(z)^j}{\sqrt{1-4z}}$$
for $z=q(1-q)$, with 
$$B_2(z)=\sum_{i=0}^{\infty}\binom{2i+1}{i}\frac1{2i+1}z^i=\frac{1-\sqrt{1-4z}}{2z}$$
and
$$B_2(z)^r=\sum_{i=0}^{\infty}\binom{2i+r}{i}\frac{r}{2i+r}z^i$$
It would be great if someone could explain this to me.
 A: 
We consider the generating functions 
  \begin{align*}
A(z)=\frac{1}{\sqrt{1-4z}}\quad\text{and}\qquad B_2(z)=\frac{1-\sqrt{1-4z}}{2z}
\end{align*}
  and derive for  non-negative integer $r$ the coefficients of
\begin{align*}
\left(B_2(z)\right)^r\qquad\text{ and }\qquad  A(z)\left(B_2(z)\right)^r
\end{align*}

We apply the following 
Change of variable formula: Let $f(z)$ be a Laurent series and $g(w)$ be a power series, $g(w)=g_1w+g_2w^2+\cdots$, where $g_1\ne 0$. Then
\begin{align*}
\color{blue}{[z^{-1}]f(z)=[w^{-1}]f(g(w))g^\prime(w)}\tag{1}
\end{align*}
See e.g. p.12 of this presentation by Ira Gessel.

Coefficients of $\left(B_2(z)\right)^r$: We use the transformation 
  \begin{align*}
z=\frac{w}{(1+w)^2}\qquad\qquad\frac{dz}{dw}=\frac{1-w}{(1+w)^3}\tag{2}
\end{align*}
and  we get 
  \begin{align*}
B_2(w)=\frac{1-\sqrt{1-\frac{4w}{(1+w)^2}}}{\frac{2w}{(1+w)^2}}=1+w
\end{align*}
We use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ a generating function $A(z)$ and obtain with (1) and (2)
  \begin{align*}
\color{blue}{[z^n]\left(B_2(z)\right)^r}&=[z^{-1}]z^{-n-1}\left(\frac{1-\sqrt{1-4z}}{2z}\right)^r\\
&=[w^{-1}]\left(\frac{w}{(1+w)^2}\right)^{-n-1}(1+w)^r\frac{1-w}{(1+w)^3}\tag{3}\\
&=[w^n](1+w)^{2n+r-1}(1-w)\tag{4}\\
&=[w^n](1+w)^{2n+r-1}-[w^{n-1}](1+w)^{2n+r-1}\tag{5}\\
&=\binom{2n+r-1}{n}-\binom{2n+r-1}{n-1}\tag{6}\\
&=\binom{2n+r}{n}-2\binom{2n+r-1}{n-1}\tag{7}\\
&=\color{blue}{\binom{2n+r}{n}\frac{r}{2n+r}}\tag{8}
\end{align*}
  and the claim follows. The coefficients $\binom{2n+1}{n}\frac{1}{2n+1}$ of $B_2(z)$  follow  by setting $r=1$.

Comment:


*

*In (3)  we use the  substitution  (2).

*In (4)  we do     some simplifications.

*In (5) we factor out and apply the rule $[z^p]z^{q}A(z)=[z^{p-q}]A(z)$.

*In (6) we select the coefficients accordingly.

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

*In (8) we do some final simplifications.
The same technique works for the other case.

Coefficients of $A(z)\left(B_2(z)\right)^r$:
We use the same transformation $z=\frac{w}{(1+w)^2}$ and we get 
  \begin{align*}
A(w)=\frac{1}{\sqrt{1-\frac{4w}{(1+w)^2}}}=\frac{1+w}{1-w}
\end{align*}
We obtain with (1) and  (2)
  \begin{align*}
\color{blue}{[z^n]\left(A(z)\left(B_2(z)\right)^r\right)}&=[z^{-1}]z^{-n-1}\frac{1}{\sqrt{1-4z}}\left(\frac{1-\sqrt{1-4z}}{2z}\right)^r\\
&=[w^{-1}]\left(\frac{w}{(1+w)^2}\right)^{-n-1}\frac{1+w}{1-w}(1+w)^r\frac{1-w}{(1+w)^3}\\
&=[w^n](1+w)^{2n+r}\\
&=\color{blue}{\binom{2n+r}{n}}
\end{align*}
  end the claim follows. The coefficients $\binom{2n}{n}$ of $A(z)$  follow  by setting $r=0$.

