2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Сумма равная последнему элементу в следующем массиве
Сообщение14.08.2024, 12:34 
Аватара пользователя


22/11/13
02/04/25
549
Пусть $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$.

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

 Профиль  
                  
 
 Re: Сумма равная последнему элементу в следующем массиве
Сообщение14.08.2024, 12:53 
Заслуженный участник


07/08/23
1055
У вас же был массив длины $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)$. И что надо проверить в данном случае?

 Профиль  
                  
 
 Re: Сумма равная последнему элементу в следующем массиве
Сообщение14.08.2024, 12:58 
Аватара пользователя


22/11/13
02/04/25
549
dgwuqtj, я специально упомянул, что
kthxbye в сообщении #1649946 писал(а):
в конце берем последний элемент массива длины $n+1$

 Профиль  
                  
 
 Re: Сумма равная последнему элементу в следующем массиве
Сообщение14.08.2024, 14:05 
Аватара пользователя


26/05/12
1694
приходит весна?
kthxbye в сообщении #1649946 писал(а):
Для $i$ от $1$ до $n-1$ и (внутри) для $j$ от $i+1$ до $n$

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

 Профиль  
                  
 
 Re: Сумма равная последнему элементу в следующем массиве
Сообщение14.08.2024, 14:13 
Аватара пользователя


22/11/13
02/04/25
549
B@R5uk, это
B@R5uk в сообщении #1649964 писал(а):
два вложенных цикла по всем возможным парам

 Профиль  
                  
 
 Re: Сумма равная последнему элементу в следующем массиве
Сообщение14.08.2024, 14:44 
Аватара пользователя


26/05/12
1694
приходит весна?
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 --

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

 Профиль  
                  
 
 Re: Сумма равная последнему элементу в следующем массиве
Сообщение14.08.2024, 14:59 
Аватара пользователя


22/11/13
02/04/25
549
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'$.

 Профиль  
                  
 
 Re: Сумма равная последнему элементу в следующем массиве
Сообщение14.08.2024, 15:28 
Заслуженный участник


07/08/23
1055
Кажется, это легко доказывается. У вас $\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$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group