The generalised Catalan Numbers and Borel's Triangle

Question

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?

Answer 1

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*}