Сумма равная последнему элементу в следующем массиве

[kthxbye]

Пусть $f(n), g(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, g(j-i)\nu_i + \nu_j]$.

Что здесь означают квадратные скобки? Они говорят о том, что действия выполняются одновременно. Т.е. вместо того, чтобы присвоить новое значение $\nu_i$, а затем присвоить новое значение $\nu_j$, мы как бы резервируем их значения как $A=\nu_i$, $B=\nu_j$, а затем в любой последовательности применяем $\nu_i=A+f(j-i)B$, $\nu_j=g(j-i)A+B$.

После множества численных экспериментов я заметил, что для абсолютно любых $f(n), g(n)$ выполняется следующее: $1+\sum\limits_{i=1}^{n}g(n-i+1)\nu_i = \nu_{n+1}$ где мы суммируем по элементам массива длины $n$, а в конце берем последний элемент массива длины $n+1$.

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

[dgwuqtj]

У вас же был массив длины $n$, откуда $\nu_{n + 1}$? При $n = 3$ вы делаете цепочку преобразований: $(1, 1, 1)$ переходит в $(f(1) + 1, g(1) + 1, 1)$, оно переходит в $(f(1) + f(2) + 1, g(1) + 1, g(2) f(1) + g(2) + 1)$, и в конце получается $(f(1) + f(2) + 1, f(1)^2 g(2) + f(1) g(2) + f(1) + g(1) + 1, f(1) g(2) + g(1)^2 + g(1) + g(2) + 1)$. И что надо проверить в данном случае?

[kthxbye]

dgwuqtj, я специально упомянул, что

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

в конце берем последний элемент массива длины $n+1$

[B@R5uk]

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

Для $i$ от $1$ до $n-1$ и (внутри) для $j$ от $i+1$ до $n$

Это один цикл со скользящей парой последовательных элементов или же два вложенных цикла по всем возможным парам?

[kthxbye]

B@R5uk, это

B@R5uk в сообщении #1649964 писал(а):

два вложенных цикла по всем возможным парам

[B@R5uk]

kthxbye, то есть сначала элемент $\nu_1$ модифицируется $n-1$ раз, затем $\nu_2$ — $n-2$ раза и так далее? Можете для однозначности понимания код выложить, которым считаете?

А вообще, для доказательства таких штук обычно ММИ используется. База есть: для $n=2$ массив будет $[f(1) + 1, g(1) + 1]$, только вашу сумму надо переписать так:

$$\nu_n=1+\sum\limits_{i=1}^{n-1}g(n-i)\nu_i$$

Она будет выражать последний элемент массива после окончания работы циклов суммирования через все предыдущие элементы. Потом принять это за допущение индукции и получить результат для массива на единицу большего размера.

-- 14.08.2024, 14:47 --

Хотя нет, что-то базы тут нету, где-то в ваших формулах ошибка. Покажите код, которым считаете.

[kthxbye]

B@R5uk в сообщении #1649973 писал(а):

kthxbye, то есть сначала элемент $\nu_1$ модифицируется $n-1$ раз, затем $\nu_2$ — $n-2$ раза и так далее?

Все верно.

Вот код на PARI/GP:

f(n) = n
g(n) = n
v(n) = my(v1); v1 = vector(n, i, 1); for(i=1, n-1, for(j=i+1, n, [v1[i], v1[j]] = [v1[i] + f(j-i)*v1[j], g(j-i)*v1[i] + v1[j]])); v1
test(n) = my(v1); v1 = v(n); 1 + sum(i=1, n, g(n-i+1)*v1[i]) == v(n+1)[n+1]

Возможно недопонимание возникает из-за того, что я по условию говорю, что у $\nu$ длина $n$, а потом той же буквой обозначаю совсем другой вектор, у которого длина $n+1$. Для него справедливо все то же самое, с поправкой, что $n$ везде возрастает на единицу. Пусть он будет тогда обозначаться как $\nu'$.

[dgwuqtj]

Кажется, это легко доказывается. У вас $\nu'_{n + 1}$ получается из $1$ последовательным прибавлением $g(n) x_1$, $g(n - 1) x_2$, и так далее, где $x_i$ — это значение $\nu'_i$ прямо перед операцией $(i, n + 1)$. Но ясно, что это значение — это в точности окончательное значение $\nu_i$ (сразу после операции $(i, n)$), так как новые операции вида $(j, n + 1)$, которые могли проводиться с $\nu'$ до $(i, n + 1)$ (то есть с $j < i$), не меняют те значения $\nu'_{j + 1}, \ldots, \nu'_n$, которые впоследствии влияют на $\nu'_i$.