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 ] 

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



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

Сейчас этот форум просматривают: DariaRychenkova


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

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