<s>[INST] The generalised Catalan Numbers and Borel's Triangle I am currently reading "Counting with Borel’s Triangle" (https://arxiv.org/abs/1804.01597), and am very confused on a stated formula.
We know:
$C_{n,k}=\frac{n-k+1}{n+1}{n+k \choose n}$
$C(x) = \sum_{n=0}^{\infty}\frac{1}{n+1}{2n \choose n}x^{n}=\frac{1-\sqrt{1-4x}}{2x}$
$C(t,x)=\sum_{n,k}C_{n,k}t^kx^n =\frac{C(tx)}{1-xC(tx)}$
$C(2,i)=\sum_{k}C_{i-1,k}2^k$
These I can completely understand the derivation of.
However, I cannot under formula (7):
$\sum_{i\geq0}C(2,i)x^i=\frac{1+2xC(2x)}{1+x}=\frac{1}{1-xC(2x)}=\frac{4}{3+\sqrt{1-8x}}$
How are these equal? Clearly, the last equals holds, but how does the first or second?  
To start, I assume we have:
$\sum_{i\geq0}C(2,i)x^i=\sum_{i\geq0}\sum_{k}C_{i-1,k}2^kx^i$
I then assume we reindex:
$\sum_{i\geq0}\sum_{k}C_{i-1,k}2^kx^i=\sum_{n+1\geq0}\sum_{k}C_{n,k}2^kx^{n+1}$
Then we can remove a factor of $x$:
$\sum_{n+1\geq0}\sum_{k}C_{n,k}2^kx^{n+1}=x\sum_{n+1\geq0}\sum_{k}C_{n,k}2^kx^{n}$
But now I am stuck. I feel like I've gone down a completely wrong path?
 [/INST] We show the validity of the equality chain
\begin{align*}
\sum_{i\geq0}C(2;i)x^i=\frac{1+2xC(2x)}{1+x}=\frac{1}{1-xC(2x)}=\frac{4}{3+\sqrt{1-8x}}
\end{align*}
with $$C(x)=\frac{1-\sqrt{1-4x}}{2x}$$  the generating  function  of   the   Catalan  numbers and the generalized Catalan numbers $C(2;i)$ stored in OEIS as A064062.

First part: $\frac{1}{1-xC(2x)}=\frac{4}{3+\sqrt{1-8x}}$
We obtain
  \begin{align*}
\color{blue}{\frac{1}{1-xC(2x)}}&=\frac{1}{1-x\left(\frac{1-\sqrt{1-8x}}{4x}\right)}\\
&=\frac{4}{4-(1-\sqrt{1-8x})}\\
&\,\,\color{blue}{=\frac{4}{3+\sqrt{1-8x}}}
\end{align*}
Second  part: $\frac{1+2xC(2x)}{1+x}=\frac{4}{3+\sqrt{1-8x}}$
We obtain
  \begin{align*}
\color{blue}{\frac{1+2xC(2x)}{1+x}}&=\frac{1}{1+x}\left(1+2x\left(\frac{1-\sqrt{1-8x}}{4x}\right)\right)\\
&=\frac{1}{1+x}\left(1+\frac{1-\sqrt{1-8x}}{2}\right)\\
&=\frac{1}{2(1+x)}\left(3-\sqrt{1-8x}\right)\\
&=\frac{1}{2(1+x)}\cdot\frac{9-(1-8x)}{3+\sqrt{1-8x}}\\
&\,\,\color{blue}{=\frac{4}{3+\sqrt{1-8x}}}
\end{align*}

For the next part it is convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series.
We start by inspecting $C(2;i)=\sum_{k=0}^{i-1}C_{i-1,k}2^k$ and looking at the relationship with the bivariate generating function
\begin{align*}
C(t;x)=\sum_{n=0}^\infty\sum_{k=0}^nC_{n,k}t^kx^k=\frac{C(tx)}{1-xC(tx)}.
\tag{1}
\end{align*}

Third part: $\sum_{i\geq0}C(2;i)x^i=\frac{1}{1-xC(2x)}$
We obtain for $i\geq 1$:
\begin{align*}
\color{blue}{C(2;i)}&=\sum_{k=0}^{i-1}C_{i-1,k}2^k\\
&=[x^{i-1}]\frac{C(2x)}{1-xC(2x)}\tag{2}\\
&=[x^i]\frac{xC(2x)}{1-xC(2x)}\\
&=[x^i]\left(\frac{1}{1-xC(2x)}-1\right)\\
&\,\,\color{blue}{=[x^i]\frac{1}{1-xC(2x)}}\tag{3}
\end{align*}
With $C(2;0)=1$ we finally obtain from (3)
  \begin{align*}
\color{blue}{\sum_{i=0}^{\infty}C(2;i)x^i}&=\sum_{i=0}^\infty[u^i]\frac{1}{1-uC(2u)}x^i\\
&\,\,\color{blue}{=\frac{1}{1-xC(2x)}}\tag{4}
\end{align*}
and the claim follows.

Comment:


*

*In (2) we evaluate (1) at $t=2$.

*In (4) we use the substitution rule
\begin{align*}
A(x)=\sum_{n=0}^\infty a_nx^n=\sum_{n=0}^\infty [u^n]A(u) x^n
\end{align*}
</s>