Binomial transform of Catalan numbers formula

Question

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, ..)$

Answer 1

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.