On a generating function and vector $\nu$ of length $n$

Question

• Let $f(n)$ be an arbitrary function with integer values.
• Let $a(n)$ be an integer sequence such that $$ \frac{1}{1-x}=\sum\limits_{n=0}^{\infty}a(n)x^n\prod\limits_{k=1}^{n+1}(1-f(k)x) $$
• Start with vector $\nu$ of length $n$ with elements $\nu_i = 1$ (that is, $\nu = \{1, 1, \dotsc, 1\}$) and for $i$ from $1$ to $n-1$ and for $j$ from $i+1$ to $n$ apply $\nu_{j} = f(i)\nu_{j-1} + \nu_{j}$.

I conjecture that after the whole transform we have vector $\nu$ with elements $\nu_i = a(i-1)$.

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

f(n) = n
upto1(n) = my(v1); v1 = vector(n, i, 1); for(i=1, n-1, for(j=i+1, n, v1[j] = f(i)*v1[j-1] + v1[j])); v1
h(n, x) = my(v1); v1 = upto1(n+1); sum(i=0, n, v1[i+1]*x^i*prod(k=1, i+1, 1-f(k)*x)) + x*O(x^n)
test(n) = my(x = 'x); Vec(h(n, x)) == vector(n+1, i, 1)

Is there a way to prove it?

Answer 1

Consider a more general problem on representing the formal power series $F:=c_0+c_1x+c_2x^2+\dots$ as the sum $$F=\sum\limits_{n=0}^{\infty}a(n)x^n\prod\limits_{k=1}^{n+1}(1-f(k)x).$$ (In your example all $c_i$ are equal to 1). We clearly have $a(0)=c_0$, and dividing by $1 - f(1)x$ and subtructing $a(0)$ we get the same kind problem of representing $G(x):=x^{-1}(F/(1-f(1)x)-c_0)$ as $$\sum\limits_{n=0}^{\infty}a(n+1)x^n\prod\limits_{k=1}^{n+1}(1-f(k+1)x).$$ The coefficients of the series $ G(x)=d_0+d_1x+d_2x^2+\dots $ satisfy the equations $$(d_0+d_1x+d_2x^2+\dots)(1-f(1)x)=(c_1+c_0f(1))+c_2x+c_3x^2+\dots ,$$ that is, $d_i-f(1)d_{i-1}=c_{i+1}$ for $i=0,1,\dots$, if we put $d_{-1}=c_0$. So, $(d)$ is obtained from $(c)$ by the first step of your algorithm for $\nu$. Then we proceed the same way.