$R$-recursion for Fibonacci numbers using signed Catalan numbers

Question

• Let $F_n$ be A000045 (i.e., Fibonacci numbers). Here $$ F_n = F_{n-1} + F_{n-2}, \\ F_0 = 0, F_1 = 1. $$
• Let $C_n$ be A000108 (i.e., Catalan numbers). Here $$ C_n = \frac{1}{n+1}\binom{2n}{n}. $$
• Let $$ R(n, q) = R(n-1, q+1) + \sum\limits_{j=0}^{q}(-1)^{q-j}C_{q-j}R(n-1, j), \\ R(0, q) = 1. $$

I conjecture that $$ R(n,0) = F_{n+2}. $$ Here is the PARI/GP program to check it numerically:

upto1(n) = my(v1, v2, v3, v4); v1 = vector(n + 1, i, 1); v2 = v1; v3 = vector(n + 1, i, 0); v3[1] = 1; v4 = vector(n, i, 0); v4[1] = 1; for(i=1, n-1, v4[i+1] = 2*(2*i-1)*v4[i]/(i+1)); for(i=1, n, for(q=0, n-i, v2[q + 1] = v1[q + 2] + sum(j=0, q, v4[q-j+1]*(-1)^(q-j)*v1[j + 1])); v1 = v2; v3[i + 1] = v1[1]); v3
upto2(n) = my(v1); v1 = vector(n+1, i, 0); v1[1] = 1; v1[2] = 2; for(i=2, n, v1[i+1] = v1[i] + v1[i-1]); v1
test(n) = upto1(n) == upto2(n)

Is there a way to prove it?

Answer 1

Let $R(x,y) = \sum_{n,q} R(n,q)x^ny^q$. Then, you can show that \begin{eqnarray*} R(x,y)\left(x - y - xyC(-y)\right) &=& x R(x,0) - yR(0,y) \\ &=& xR(x,0) - \frac{y}{1-y} \end{eqnarray*}

where $C(x)$ is the generating function for the Catalan numbers. $$ C(x) = \frac{1 - \sqrt{1-4x}}{2x} $$ Substituting gives $$ R(x,y) \left( \frac{x}{2}(\sqrt{1+4y} + 1) - y\right) = x R(x,0) - \frac{y}{1-y} $$ Set $y = x(x+1)$, and the left side vanishes giving $$ R(x,0) = \frac{x+1}{1 - x - x^2} $$ which is the generating function for the Fibonacci numbers.