<s>[INST] Binomial transform of Catalan numbers formula How to prove that OEIS A007317 Binomial transform of Catalan numbers $a_{n}: 1, 2, 5, 15, 51, 188, 731, 2950, 12235, 51822, .. (n = 1, 2, ..)$ has a recurrence formula: $(n+2)a_{n+2} = (6n+4)a_{n+1} - (5n)a_{n}$ ? 
The sequence is defined as: $a_{n+1} = \sum_{k=0}^{n} \binom{n}{k}c_{k}$ where $c_{n} = \frac{1}{n+1}\binom{2n}{n}$ is OIES A000108 Catalan numbers: $1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, .. (n = 0, 1, ..)$
 [/INST] We prove the recurrence formula with the help of generating functions. Let $A(z)$ be the generating functions of the $a_n$
\begin{align*}
A(z)=\sum_{n=1}^\infty a_nz^n=\sum_{n=0}^\infty a_{n+1}z^{n+1}
=\sum_{n=0}^\infty \left(\sum_{k=0}^n\binom{n}{k}C_k \right)z^{n+1}
\end{align*}
and let $C(z)$ be the (well-known) generating function of the Catalan numbers $C_n$
\begin{align*}
C(z)&=\sum_{n=0}^{\infty} C_nz^n=\sum_{n=0}^{\infty} \frac{1}{n+1}\binom{2n}{n}=\frac{1}{2z}\left(1-\sqrt{1-4z}\right)
\end{align*}
We prove the claim in three steps. Since the $a_n$ are a binomial transform of $C_n$, we derive at first a corresponding functional equation between $A(z)$ and $C(z)$. From this functional equation we obtain an explicit expression of $A(z)$. In the last step we use $A(z)$ to show that the corresponding generating function of the left hand and the right hand side of the recurrence relation coincide.

Step 1: Functional equation between $A(z)$ and $C(z)$
The following is valid
  \begin{align*}
A(z)=\frac{z}{1-z}C\left(\frac{z}{1-z}\right)\tag{1}
\end{align*}
We obtain
\begin{align*}
\frac{z}{1-z}C\left(\frac{z}{1-z}\right)&=\frac{z}{1-z}\sum_{k=0}^{\infty}C_k\left(\frac{z}{1-z}\right)^k\\
&=\sum_{k=0}^{\infty}C_k\left(\frac{z}{1-z}\right)^{k+1}\\
&=\sum_{k=0}^{\infty}C_kz^{k+1}(1-z)^{-(k+1)}\\
&=\sum_{k=0}^{\infty}C_kz^{k+1}\sum_{l=0}^{\infty}\binom{-(k+1)}{l}(-z)^l\tag{2}\\
&=z\sum_{k=0}^{\infty}C_kz^{k}\sum_{l=0}^{\infty}\binom{k+l}{l}z^l\tag{3}\\
&=z\sum_{n=0}^{\infty}\left(\sum_{{k+l=n}\atop{k,l\geq 0}}\binom{k+l}{l}C_k\right)z^n\tag{4}\\
&=z\sum_{n=0}^{\infty}\left(\sum_{k=0}^n\binom{n}{n-k}C_k\right)z^n\tag{5}\\
&=\sum_{n=0}^{\infty}\left(\sum_{k=0}^n\binom{n}{k}C_k\right)z^{n+1}\\
&=A(z)\\
\end{align*}

Comment:


*

*In (2) we use the binomial series

*In (3) we use the relation $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$

*In (4) we multiply the series (Cauchy product)

*In (5) we replace $l$ with $n-k$

Step 2: Explicit expression of $A(z)$
The following is valid
  \begin{align*}
A(z)=\frac{1}{2}\left(1-\sqrt{\frac{1-5z}{1-z}}\right)
\end{align*}
Based upon the generating function $C(z)=\frac{1}{2z}\left(1-\sqrt{1-4z}\right)$ of the Catalan numbers we obtain from (1)
\begin{align*}
A(z)&=\frac{z}{1-z}C\left(\frac{z}{1-z}\right)\\
&=\frac{z}{1-z}\cdot\frac{1}{2\left(\frac{z}{1-z}\right)}\left(1-\sqrt{1-\frac{4z}{1-z}}\right)\\
&=\frac{1}{2}\left(1-\sqrt{\frac{1-5z}{1-z}}\right)\\
\end{align*}

$$ $$

Step 3: Recurrence relation
The following recurrence relation is valid
\begin{align*}
&(n+2)a_{n+2}=(6n+4)a_{n+1}-5na_n\qquad\qquad n\geq 0\\
&a_0=0, a_1=1
\end{align*}

We take the left hand and right hand side of the recurrence relation, use an Ansatz with the generating function
\begin{align*}
A(z)=\sum_{n=1}^{\infty}a_n z^n=\frac{1}{2}\left(1-\sqrt{\frac{1-5z}{1-z}}\right)
\end{align*}
and show that both sides coincide. We will also use the derivative of $A(z)$
\begin{align*}
\frac{d}{dz}A(z)=\sqrt{\frac{1-z}{1-5z}}\frac{1}{(1-z)^2}
\end{align*}

We start with the left hand side
\begin{align*}
\sum_{n=0}^\infty(n+2)a_{n+2}z^n&=\sum_{n=2}^\infty na_{n}z^{n-2}\\
&=\frac{1}{z}\frac{d}{dz}\left(\sum_{n=2}^{\infty}a_nz^n\right)\\
&=\frac{1}{z}\frac{d}{dz}\left(A(z)-z\right)\\
&=\frac{1}{z}\sqrt{\frac{1-z}{1-5z}}\frac{1}{(1-z)^2}-\frac{1}{z}\tag{6}
\end{align*}
and we obtain from the right hand side
\begin{align*}
\sum_{n=0}^\infty&(6n+4)a_{n+1}z^n-\sum_{n=0}^{\infty}5na_nz^n\\
&=\sum_{n=1}^\infty(6n-2)a_{n}z^{n-1}-5z\sum_{n=0}^{\infty}na_nz^{n-1}\\
&=6\sum_{n=1}^\infty na_{n}z^{n-1}-2\sum_{n=1}^\infty a_{n}z^{n-1}-5z\sum_{n=0}^{\infty}na_nz^{n-1}\\
&=6\frac{d}{dz}\sum_{n=1}^{\infty}a_nz^n-\frac{2}{z}A(z)-5z\frac{d}{dz}\sum_{n=1}^{\infty}a_nz^n\\
&=(6-5z)\frac{d}{dz}A(z)-\frac{2}{z}A(z)\\
&=\frac{6-5z}{(1-z)^2}\sqrt{\frac{1-z}{1-5z}}-\frac{1}{z}\left(1-\sqrt{\frac{1-5z}{1-z}}\right)\\
&=\sqrt{\frac{1-z}{1-5z}}\left(\frac{6-5z}{(1-z)^2}+\frac{1}{z}\cdot\frac{1-5z}{1-z}\right)-\frac{1}{z}\\
&=\frac{1}{z}\sqrt{\frac{1-z}{1-5z}}\frac{1}{(1-z)^2}-\frac{1}{z}\tag{7}
\end{align*}
We see the generating functions (6) and (7) of the left-hand and right-hand side coincide showing the validity of the recurrence relation.

</s>