Формула суммы натуральных чисел от 1 до N в степени a

Rhein · Сообщение **Rhein** » 03 апр 2007, 21:53

Допустим я хочу знать формулу (разумеется в виде полинома), которой задаётся сумма ряда
натуральных чисел от 1 до N в степени a.
1^a+2^a+3^a+....+n^a
для a=8 и меньше я их знаю, вот хочу найти для 9 и далее.
B какой плоскости разрешается данная задача?

AV_77 · Сообщение **AV_77** » 04 апр 2007, 01:03

Rhein писал(а):Source of the post
Допустим я хочу знать формулу (разумеется в виде полинома), которой задаётся сумма ряда
натуральных чисел от 1 до N в степени a.
1^a+2^a+3^a+....+n^a
для a=8 и меньше я их знаю, вот хочу найти для 9 и далее.
B какой плоскости разрешается данная задача?

Эти формулы можно найти, например, индукцией. Пусть

$p_k(n) = 1^k + 2^k + \ldots + n^k.$

Тогда

$p_k(n) = 1 + (1+1)^k + \ldots + (1 + (n-1))^k = \\ = n + C_k^1 p_1(n-1) + C_k^2 p_2(n-1) + \ldots + C_k^{k-1} p_{k-1}(n-1) + p_k(n-1) = \ldots = \\ = p_1(n) + C_k^1 \sum_{j=1}^{n-1} p_1(j) + C_k^2 \sum_{j=1}^{n-1} p_2(j) + \ldots + C_k^{k-1} \sum_{j=1}^{n-1} p_{k-1}(j).$

Осталось научиться находить суммы вида
$p_k(1) + p_k(2) + \ldots + p_k(n).$

A вообще эта задача решается следующим образом. Поясню на примере.
Пусть нам нужно найти $$ p_3(n). $$

Составим таблицу

$0 \\ \quad\quad\quad 1 \\ 1 \quad\quad\quad \quad 6\quad\quad \\ \quad\quad\quad 7 \quad\quad\quad 6 \\ 8 \quad\quad\quad 12 \quad\quad\quad 0 \\ \quad\quad\quad 19 \quad\quad\quad 6 \\ 27 \quad\quad\quad 18 \\ \quad\quad\quad 37 \\ 64$

Получаем

$p_3(n) = C_n^1 \cdot 0 + C_n^2 \cdot 1 + C_n^3 \cdot 6 + C_n^4 \cdot 6.$

Каждый элемент следующего столбца таблицы, как нетрудно заметить, равен разности двух соседних элементов в левом от него столбце.
Первый столбец - числа $$ 1^3, 2^3, ..., 4^3. $$

B качестве множителей при $$ C_n^1, C_n^2, ... $$

берутся первые элементы соответствующих столбцов.

Natrix · Сообщение **Natrix** » 04 апр 2007, 01:36

Rhein писал(а):Source of the post
Допустим я хочу знать формулу (разумеется в виде полинома), которой задаётся сумма ряда
натуральных чисел от 1 до N в степени a.
1^a+2^a+3^a+....+n^a
для a=8 и меньше я их знаю, вот хочу найти для 9 и далее.
B какой плоскости разрешается данная задача?

==========Бездоказательное утверждение==========

1. Сумма такая всегда многочлен степени a+1 от n.

==================================================
Ha калькуляторе находишь a+2 значений многочлена и применяешь, дай, Боже, памяти, конечные разности.
И твоя задача решена!...Теоретически... Вот, вот...To, что AV_77 прописал в предыдущем посте

AV_77 · Сообщение **AV_77** » 04 апр 2007, 01:38

Natrix писал(а):Source of the post
Rhein писал(а):Source of the post
Допустим я хочу знать формулу (разумеется в виде полинома), которой задаётся сумма ряда
натуральных чисел от 1 до N в степени a.
1^a+2^a+3^a+....+n^a
для a=8 и меньше я их знаю, вот хочу найти для 9 и далее.
B какой плоскости разрешается данная задача?

==========Бездоказательное утверждение==========

1. Сумма такая всегда многочлен степени a+1 от n.

==================================================
Ha калькуляторе находишь a+2 значений многочлена и применяешь, дай, Боже, памяти, конечные разности.
И твоя задача решена!...Теоретически...

Второе приведенное решение как раз и есть построение такого многочлена в общем виде(пример c $$ p_3(n) $$

).
Причем как раз используются конечные разности.

vladb314 · Сообщение **vladb314** » 18 июл 2007, 12:38

AV_77 писал(а):Source of the post
A вообще эта задача решается следующим образом. Поясню на примере.
Пусть нам нужно найти Составим таблицу

$0 \\ \quad\quad\quad 1 \\ 1 \quad\quad\quad \quad 6\quad\quad \\ \quad\quad\quad 7 \quad\quad\quad 6 \\ 8 \quad\quad\quad 12 \quad\quad\quad 0 \\ \quad\quad\quad 19 \quad\quad\quad 6 \\ 27 \quad\quad\quad 18 \\ \quad\quad\quad 37 \\ 64$

Получаем

$p_3(n) = C_n^1 \cdot 0 + C_n^2 \cdot 1 + C_n^3 \cdot 6 + C_n^4 \cdot 6.$

Каждый элемент следующего столбца таблицы, как нетрудно заметить, равен разности двух соседних элементов в левом от него столбце.
Первый столбец - числа
B качестве множителей при берутся первые элементы соответствующих столбцов.

Извините, пожалуйста, но я так и не понял, получается, что полученная формула применима только для n>=4 ? Кстати, я проверил, при n = 4 получается, что $$ p_3(n) = 36 $$

, однако $1^3+2^3+3^3+4^3 = 36 +4^3 \ne 36$

AV_77 · Сообщение **AV_77** » 19 июл 2007, 00:14

vladb314 писал(а):Source of the post
AV_77 писал(а):Source of the post
$p_3(n) = C_n^1 \cdot 0 + C_n^2 \cdot 1 + C_n^3 \cdot 6 + C_n^4 \cdot 6.$

Извините, пожалуйста, но я так и не понял, получается, что полученная формула применима только для n>=4 ? Кстати, я проверил, при n = 4 получается, что , однако $1^3+2^3+3^3+4^3 = 36 +4^3 \ne 36$

Если Вы обратили внимание, то сумма (первый столбец) начинается c 0, т.e. $$ p_3(n) $$

означает

.

vladb314 · Сообщение **vladb314** » 19 июл 2007, 09:51

AV_77 писал(а):Source of the post
означает
.

Ясно. Спасибо.
A при n < 4, например, при n = 3, получаем, что $p_3(n) = p_3(3) = C_3^1 \cdot 0 + C_3^2 \cdot 1 + C_3^3 \cdot 6 + C_3^4 \cdot 6 = 0 + 3 + 6 + 0 = 9$
Всё ясно.

yourdomain.com