Последний элемент массива и цепная дробь

[kthxbye]

Пусть $f(n)$ это произвольная функция с целочисленными значениями.

Пусть $a(n)$ это целочисленная последовательность с производящей функцией $\frac{1}{G(0,x)}$, где $G(0,x)$ это цепная дробь, такая, что

$$ G(k,x) = 1 - \cfrac{f(k+1)x}{G(k+1, x)}. $$

Заметьте, что

$$ G(0, x) = 1 - \cfrac{f(1)x}{1 - \cfrac{f(2)x}{1 - \cfrac{f(3)x}{1 - \cfrac{f(4)x}{\ddots}}}}. $$

Пусть $b(n)$ это целочисленная последовательность, такая, что

$$ b(n) = \sum\limits_{i=0}^{n-1}a(n-i-1)b(i), \\ b(0) = 1. $$

Пусть $c(n)$ это то же, что и $\nu_n$ (после полной трансформации), где мы начинаем с массива $\nu$ длины $n$ с элементами $\nu_i = 1$. Для $i$ от $1$ до $n-1$ и (внутри) для $j$ от $i+1$ до $n$ (т.е. это два вложенных цикла) будем последовательно применять $[\nu_i, \nu_j] = [\nu_i + f(j-i)\nu_j, \nu_i + f(j-i)\nu_j]$.

После множества численных экспериментов я заметил, что для абсолютно любой $f(n)$ выполняется следующее: $b(n) = c(n)$.

Вот код на PARI/GP для проверки:

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)

Существует ли способ как-нибудь доказать это?

[kthxbye]

Только что заметил, что гипотезу можно переформулировать следующим образом:

Пусть задан вектор $\nu$ длины $n$ с элементами $\nu_i=1$. Для $i$ от $1$ до $n-1$ и (внутри) для $j$ от $1$ до $n-i$ (т.е. это два вложенных цикла) будем последовательно применять $\nu_{i+j} = \nu_{i+j-1} + f(j)\nu_{i+j}$.

После полной трансформации будем иметь массив $\nu$ с элементами $\nu_i = b(i)$.

Вот код на PARI/GP для проверки:

f(n) = n
upto1(n) = my(v1); v1 = vector(n, i, 1); for(i=1, n-1, for(j=1, n-i, v1[i+j] = v1[i+j-1] + f(j)*v1[i+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)

[kthxbye]

kthxbye в сообщении #1650177 писал(а):

Для $i$ от $1$ до $n-1$ и (внутри) для $j$ от $1$ до $n-i$ (т.е. это два вложенных цикла) будем последовательно применять $\nu_{i+j} = \nu_{i+j-1} + f(j)\nu_{i+j}$.

Вот тут можно поменять на $j$ от $i+1$ до $n$, и тогда будет почти как в оригинале: $\nu_j = \nu_{j-1} + f(j-i)\nu_j$.

Кроме того, я обнаружил упрощение вопроса. Судя по всему, производящая функция для $b(n)$ это $\frac{1}{G_1(0,x)}$ где $G_1(0,x)$ это цепная дробь, такая, что

$$G_1(k,x) = 1 - \cfrac{f(k)x}{G_1(k+1, x)}.$$

Заметьте, что

$$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}}}}.$$

Здесь мы просто дополнительно задаем $f(0)=1$.

Такая интерпретация позволяет вместо работы с двумя различными объектами (цепной дробью и суммой), сфокусироваться лишь на цепной дроби.

К слову, некий Федор Петров ответил на мой другой вопрос, сведя его к повторяющейся операции и связав ее с шагами моего алгоритма. Я дополнительно попросил его посмотреть и на этот вопрос (который я также опубликовал на MO), но он либо еще не прочитал мою просьбу, либо же вопрос оказался слишком сложным для него.

Может быть здесь тоже можно обнаружить какую-то повторяющуюся операцию?