General case of the some $R$-recursions

Question

• Let $f(n)$ be an arbitrary function.

• Let $a(n)$ be an integer sequence such that its ordinary generating function satisfies $$ A(x)=\sum\limits_{i=0}^{\infty}\frac{x^i}{\prod\limits_{j=0}^{i}(1-f(j)x)} $$

• Let $$ R(n, q) = f(q)R(n-1,q) + R(n-1, q+1), \\ R(0, q) = 1 $$

I conjecture that $$R(n, 0) = a(n).$$

Here is the PARI/GP program to check it numerically:

f(n) = n
a_upto(n) = Vec(sum(i = 0, n, x^i / prod(j = 0, i, 1 - f(j)*x)) + x*O(x^n))
R_upto(n) = my(v1, v2, v3); v1 = vector(n + 1, i, 1); v2 = v1; v3 = vector(n + 1, i, 0); v3[1] = 1; for(i = 1, n, for(q = 0, n - i, v2[q + 1] = f(q) * v1[q + 1] + v1[q + 2]); v1 = v2; v3[i + 1] = v1[1]); v3
test(n) = a_upto(n) == R_upto(n)

Is there a way to prove it?

Answer 1

Let $$ A(x,q)=\sum_{i=0}^{\infty}\frac{x^i}{\prod\limits_{j=0}^{i}(1-f(q+j)x)}, $$ so that $A(x) = A(x,0)$. Define $a(n,q)$ by $$A(x,q) = \sum_{n=0}^\infty a(n,q) x^n,$$ so that $a(n) = a(n,0)$. I will show that $a(n,q) = R(n,q)$, which implies $a(n)=R(n,0)$.

We have $$A(x,q) = \frac{1}{1-f(q)x}\Bigl(1+x A(x,q+1)\Bigr)$$ so $$A(x,q) - f(q)x A(x,q) = 1+xA(x,q+1).$$ Equating coefficients of $x^n$ on both sides gives $a(0,q)=1$ and $$a(n,q) - f(q)a(n-1,q) = a(n-1,q+1)$$ for $n>0$. Therefore $a(n,q) = R(n,q)$, as claimed.