Return to Question

Please note that this question has been completely reworked in order not to overload it with unnecessary and useless information.

• Let $f(n)$ be an arbitrary function with integer values.
• Let $a(n)$ be an integer sequence with generating function $\frac{1}{U(x)}$ such that $$ U(x) = 1 - \cfrac{f(0)x}{1 - \cfrac{f(1)x}{1 - \cfrac{f(2)x}{1 - \cfrac{f(3)x}{\ddots}}}}. $$
• 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(j-i-1)\nu_{j} + [j>(i+1)]\nu_{j-1}$.

Here square bracket denotes Iverson bracket.

I conjecture that after the whole transform we have $$ \nu_n = a(n-1). $$

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

f(n) = 2*n + 10
upto1(n) = my(v1); v1 = vector(n, i, 1); for(i=1, n-1, for(j=i+1, n, v1[j] = f(j-i-1)*v1[j] + (j>(i+1))*v1[j-1])); v1
U(n,x) = my(CF = 1); for(i=1, n, CF = 1 - f(n - i)*x/CF + x*O(x^n)); CF
upto2(n) = my(v1); v1 = Vec(1/U(n,x))
test1(n) = upto1(n+1) == upto2(n)

Is there a way to prove it?

Please note that this question has been completely reworked in order not to overload it with unnecessary and useless information.

• Let $f(n)$ be an arbitrary function with integer values.
• Let $a(n)$ be an integer sequence with generating function $\frac{1}{U(x)}$ such that $$ U(x) = 1 - \cfrac{f(0)x}{1 - \cfrac{f(1)x}{1 - \cfrac{f(2)x}{1 - \cfrac{f(3)x}{\ddots}}}}. $$
• 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(j-i-1)\nu_{j} + [j>(i+1)]\nu_{j-1}$.

Here square bracket denotes Iverson bracket.

I conjecture that after the whole transform we have $$ \nu_n = a(n-1). $$

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

f(n) = 2*n + 10
upto1(n) = my(v1); v1 = vector(n, i, 1); for(i=1, n-1, for(j=i+1, n, v1[j] = f(j-i-1)*v1[j] + (j>(i+1))*v1[j-1])); v1
U(n,x) = my(CF = 1); for(i=1, n, CF = 1 - f(n - i)*x/CF + x*O(x^n)); CF
upto2(n) = my(v1); v1 = Vec(1/U(n,x))
test1(n) = upto1(n+1) == upto2(n)

In addition, this question can be rephrased as follows:

• Let $P(n,k)$ be a triangle read by rows such that $$ P(n, k) = \begin{cases} 0 & \textrm{if } k > n \\ 1 & \textrm{if } k = 0 \\ P(n-1, k) + f(n-k)P(n, k-1) & \textrm{otherwise} \end{cases} $$

I conjecture that $$ P(n,n)=a(n). $$

Is there a way to prove it?

• Let $f(n)$ be an arbitrary function with integer values.
• Let $a(n)$ be an integer sequence with ordinary generating function $\frac{1}{G(0,x)}$ where $G(0,x)$ is a continued fraction such that $$ G(k,x) = 1 - \cfrac{f(k+1)x}{G(k+1, x)}. $$ Note that $$ G(0, x) = 1 - \cfrac{f(1)x}{1 - \cfrac{f(2)x}{1 - \cfrac{f(3)x}{1 - \cfrac{f(4)x}{\ddots}}}}. $$
• Let $b(n)$ be an integer sequence such that $$ b(n) = \sum\limits_{i=0}^{n-1}a(n-i-1)b(i), \\ b(0) = 1. $$
• Let $c(n)$ be $\nu_n$ (after the whole transform) where we 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_i, \nu_j] = [\nu_i + f(j-i)\nu_j, \nu_i + f(j-i)\nu_j]$.

I conjecture that $$ b(n) = c(n). $$

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

f(n) = n
c(n) = my(v1); v1 = vector(n, i, 1); for(i=1, n-1, for(j=i+1, n, A = v1[i] + f(j-i)*v1[j]; v1[i] = A; v1[j] = A)); v1[n]
upto1(n) = my(v1); v1 = vector(n, i, c(i))
h(n,x) = my(CF = 1); for(i=1, n, CF = 1 - f(n - i + 1)*x/CF + x*O(x^n)); 1/CF
upto2(n) = my(v1); v1 = Vec(h(n,x)); v2 = vector(n+1, i, 0); v2[1] = 1; for(i=1, n, v2[i+1] = sum(j=0, i-1, v2[j+1]*v1[i-j])); v2 = vector(n, i, v2[i+1])
test(n) = upto1(n) == upto2(n)

UPD1:

Given conjecture can be reformulated as follows:

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} = \nu_{j-1} + f(j-i)\nu_{j}$.

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

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] = v1[j-1] + f(j-i)*v1[j])); v1
h(n,x) = my(CF = 1); for(i=1, n, CF = 1 - f(n - i + 1)*x/CF + x*O(x^n)); 1/CF
upto2(n) = my(v1); v1 = Vec(h(n,x)); v2 = vector(n+1, i, 0); v2[1] = 1; for(i=1, n, v2[i+1] = sum(j=0, i-1, v2[j+1]*v1[i-j])); v2 = vector(n, i, v2[i+1])
test(n) = upto1(n) == upto2(n)

UPD2:

It also looks like that ordinary generating function for $b(n)$ is $\frac{1}{G_1(0,x)}$ where $G_1(0,x)$ is a continued fraction such that $$ G_1(0,x)=1-\frac{x}{G(0,x)} $$ In other words, we have $$ G_1(k,x)=1-\frac{f(k)x}{G_1(k+1,x)} $$ Note that $$ G_1(0, x) = 1 - \cfrac{f(0)x}{1 - \cfrac{f(1)x}{1 - \cfrac{f(2)x}{1 - \cfrac{f(3)x}{\ddots}}}}. $$ Here we just need to set $f(0)=1$.

I think this interpretation is simpler because it allows you to focus on the continued fraction, rather than on two different things (namely the continued fraction and the sum).

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

f(n) = if(n == 0, 1, n)
upto1(n) = my(v1); v1 = vector(n, i, 1); for(i=1, n-1, for(j=i+1, n, v1[j] = v1[j-1] + f(j-i)*v1[j])); v1
h(n,x) = my(CF = 1); for(i=1, n, CF = 1 - f(n - i)*x/CF + x*O(x^n)); 1/CF
upto2(n) = my(v1); v1 = Vec(h(n,x)); v1 = vector(n, i, v1[i+1])
test(n) = upto1(n) == upto2(n)

UPD3:

It turns out that $f(0)$ can be any number. We just need to change starting $\nu_i=1$ to $\nu_i=f(0)$ and also multiply $\nu_{j-1}$ by $f(0)$ at the first step of each cycle for $j$.

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

f(n) = if(n == 0, 100, n)
upto1(n) = my(v1); v1 = vector(n, i, f(0)); for(i=1, n-1, v1[i+1] = f(1)*v1[i+1] + f(0)*v1[i]; for(j=i+2, n, v1[j] = f(j-i)*v1[j] + v1[j-1])); v1
h(n,x) = my(CF = 1); for(i=1, n, CF = 1 - f(n - i)*x/CF + x*O(x^n)); 1/CF
upto2(n) = my(v1); v1 = Vec(h(n,x)); v1 = vector(n, i, v1[i+1])
test1(n) = upto1(n) == upto2(n)

Please note that this question has been completely reworked in order not to overload it with unnecessary and useless information.

• Let $f(n)$ be an arbitrary function with integer values.
• Let $a(n)$ be an integer sequence with generating function $\frac{1}{U(x)}$ such that $$ U(x) = 1 - \cfrac{f(0)x}{1 - \cfrac{f(1)x}{1 - \cfrac{f(2)x}{1 - \cfrac{f(3)x}{\ddots}}}}. $$
• 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(j-i-1)\nu_{j} + [j>(i+1)]\nu_{j-1}$.

Here square bracket denotes Iverson bracket.

I conjecture that after the whole transform we have $$ \nu_n = a(n-1). $$

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

f(n) = 2*n + 10
upto1(n) = my(v1); v1 = vector(n, i, 1); for(i=1, n-1, for(j=i+1, n, v1[j] = f(j-i-1)*v1[j] + (j>(i+1))*v1[j-1])); v1
U(n,x) = my(CF = 1); for(i=1, n, CF = 1 - f(n - i)*x/CF + x*O(x^n)); CF
upto2(n) = my(v1); v1 = Vec(1/U(n,x))
test1(n) = upto1(n+1) == upto2(n)

Is there a way to prove it?

UPD3:

It turns out that $f(0)$ can be any number. We just need to change starting $\nu_i=1$ to $\nu_i=f(0)$ and also multiply $\nu_{j-1}$ by $f(0)$ at the first step of each cycle for $j$.

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

f(n) = if(n == 0, 100, n)
upto1(n) = my(v1); v1 = vector(n, i, f(0)); for(i=1, n-1, v1[i+1] = f(1)*v1[i+1] + f(0)*v1[i]; for(j=i+2, n, v1[j] = f(j-i)*v1[j] + v1[j-1])); v1
h(n,x) = my(CF = 1); for(i=1, n, CF = 1 - f(n - i)*x/CF + x*O(x^n)); 1/CF
upto2(n) = my(v1); v1 = Vec(h(n,x)); v1 = vector(n, i, v1[i+1])
test1(n) = upto1(n) == upto2(n)

Is there a way to prove it?