tguev Jul 3 at 10:08

Сумма степеней натурального ряда. Часть 1

Medium

4 min

11K

Entertaining tasksAlgorithms*Mathematics*

+46

Comments 35

Eduard_88 Jul 3 at 10:13

Как всегда все расписано очень доступным языком)

UFO just landed and posted this here

Krotesk Jul 3 at 10:43

...

Alexandroppolus Jul 3 at 14:58

Когда-то придумал такой трудоемкий, но рабочий способ (на первенство, разумеется, не претендую 😁):

$\sum_{i=1}^{n}(i^{k+1}-(i-1)^{k+1}) = n^{k+1}$

Если слева раскрыть бином Ньютона и сократить степени (k+1), то можно выразить сумму ряда для степени k через суммы для всех предыдущих степеней. Тут, кстати, и гипотеза подтверждается. (сорри, если проспойлерил кусок второй части статьи)

А насчет геометрических способов - видел охренительное решение для суммы обратных квадратов.

lgorSL Jul 4 at 18:44

У Кнута есть книжка "Дискретная математика", там очень красиво рассказывается про аналогии между интегралом и суммой ряда. И в другую сторону тоже - элементы ряда это аналоги производной от суммы ряда. И заодно красиво переносятся теоремы и подходы для решения задач.

Есть некоторые отличия - например, для непрерывной функции производная считается по бесконечно малой окрестности точки, а для ряда так не прокатит, там шаг останется либо в +1, либо в -1 (и производная ряда "слева" может отличаться от производной "справа").

Вы в своём способе как раз написали производную от суммы ряда)

ivan_kolivan Jul 3 at 14:59

Конечно, графический метод нельзя использовать в качестве доказательства (если не дополнить его использованием метода мат.индукции), но он очень наглядно и доступно демонстрирует с виду неинтуитивные формулы. Спасибо!

nickolaym Jul 3 at 15:12

Все эти штуковины решаются однообразно с помощью алгебры.

Допустим, сумма p-й степени чисел - это полином (p+1)-й степени.

$\sum_{k=1..n}k^p = P_{p+1}(n) = a_0 + a_1 n + a_2 n^2 + ... + a_p n^p$

И решаем уравнение "для произвольного n", получаемое из утверждения индукции.

$P_{p+1}(n+1) = P_{p+1}(n) + (n+1)^p$

которое рассыпается на систему уравнений над переменными a[k].

Странно, что для четвёртой степени потребовалась тысяча лет. Ну да это, наверно, влияние пифагоровского очарования целочисленно-геометрическими методами.

Mingun Jul 3 at 18:47

В первой формуле забыли член $a_{p + 1} n^{p + 1}$ к сумме дописать.

tarlex2001 Jul 4 at 12:51

Не имеет никакого смысла решать систему уравнений . Гораздо проще восстановить любую формулу для суммы , используя следующее, легко доказываемое утверждение : имеем произвольный многочлен f (x ) ( в частном случае - просто степень ) , если возмем сумму значений этого многочлена от натуральных чисел до некоторого " n " , то будем иметь некий многочлен g( n ) , тогда сумма производных многочлена f от натуральных чисел до некоторого " n " будет равна производной многочлена g ( n ) плюс некоторая константа .

Данный способ нахождения сумм , однозначно проще , быстрее и просто - элементарнее , чем как всевозможные рекуретные формулы для данных сумм , так и их выражение через числа Бернули , которые в свою очередь требуют рекурентные соотношения для них самих .

wataru Jul 4 at 13:23

Очень интересное наблюдение!

Это не так очевидно, что можно менять местами производную и суммирование. Это можно доказать, например, если задать g(x) = sum i=1..[x] f(x-[x]+i), а дальше посчитать производную по определению через пределы.

В итоге это выражается в следующий метод: имея коэффициенты полинома для суммы степеней k, надо скопировать коэффициенты предыдущего полинома, сдвинуть на 1 влево, домножить их на (k-1) и поделить на степень при коэффициенте. Домножение происходит из-за взятия производной f. Деление - из-за интеграла g'. Последний коэффициент подбирается вручную так, чтобы сумма их всех была 1 (это если подставить сумму из одного элемента):

k=0: g0(x)=1*x

1*1/2 = 1/2
1 - 1/2 = 1/2
k=1: g1(x)=1/2x^2 + 1/2*x

1/2*2/3 = 1/3
1/2*2/2 = 1/2
1-1/3-1/2=1/6
k=2: g2(x)=1/3x^3 + 1/2x^2 + 1/6x

1/3*3/4 = 1/4
1/2*3/3 = 1/2
1/6*3/2 = 1/4
1 - 1/4 - 1/2 - 1/4 = 0
k=3: g3(x)=1/4x^4 + 1/2x^3 + 1/4x^2+0x

1/4*4/5 = 1/5
1/2*4/4 = 1/2
1/4*4/3=1/3
0*4/2 = 0
1 = 1/5 - 1/2 - 1/3 = -1/30
k=4: g4(x)=1/5x^5+1/2x^4+1/3x^3+0x^2-1/30x

Еще, альтернативно можно просто домножить прудыдущий полином на k-1 и проинтегрировать его. Так одновременно произойдет и сдвиг и деление на i. Последний коэффициент все равно придется подбирать вручную.

Уверен, эти же выражения можно вывести и через составление уравнений, но пока непонятно, как.

tarlex2001 Jul 4 at 14:18

Не так очевидно для бесконечных рядов...Впрочем и там вопрос решается через анализ равномерной сходимости ряда . Но у нас- то , конечные суммы...

И потом : вопрос не в изменении последовательности операций .

Итак : пусть сумма многочлена f ( x ) по натуральным значениям до некоторого " n " есть многочлен g( n ) .

g ( n ) - g ( n-1 ) = f ( n ) . То есть равенство выполняется в бесконечном числе точек . А ведь это всего лишь многочлен... То есть выражение слева и справа - одно и то - же . То есть это один и тот - же многочлен , просто выражен по разному . Поэтому это равенство верно и для производных . Далее суммируем левую и правую части ( уже производных ) и замечаем , что левая сумма это всего лишь производная g( n ) минус производная g ( 0 ) - то бишь константа ... Что и требовалось доказать...

Дальнейшее понятно - зная например сумму натуральных чисел до " n " , легко получаем сумму их квадратов , используя данное утверждение . И т.д.

Более того : используя данный факт , очень легко получаются рекуретные соотношения для самих сумм напрямую .

Тем не менее согласен - вместо оперирования с многочленами , проще оперировать просто с коэффициентами , но это сработает лишь для степеней . А данный алгоритм позволяет оперировать вообще с любыми многочленами...

id_potassium_chloride Jul 23 at 16:31

Я сейчас нахожусь в условиях медленного и нестабильного Интернета и от скуки решил взяться за бумажку и ручку. Для суммы четвёртых степеней без особого труда получил формулу примерно таким же способом. Я польщён умением автора строить треугольники, но каждый раз я смотрел на это как на вытаскивание кролика из шляпы. Алгебраический способ через индукцию кажется мне на порядок проще.

Думаю, примерно так исторически эти формулы и получались, а на изобретение привычного нам алгебраического метода потребовалась тысяча лет как раз из-за того, что сами понятия "неизвестной" или "переменной" появились только в Европе в XVI-XVII веках. Думаю, дело в этом

wataru Jul 3 at 15:33

Тут кстати, можно заметить замечательный факт:

$\sum_{i=1}^n i^3 = \left(\sum_{i=1}^n i \right)^2 = n^2(n+1)^2/4$

Что, к тому же, истинно и в неприрывном случае:

$\int x^3dx = \left(\int xdx\right)^2 = x^4/4$

Stiver Jul 3 at 17:03

Коэффициенты в формуле суммы можно легко посчитать из треугольника Паскаля. Ниже на примере k = 3.

Пусть наша искомая формула a4*n^4 + a3*n^3 + a2*n^2 + a1*n
Рисуем треугольник Паскаля на боку:

1 1 1 1 1
   1 2 3 4
      1 3 6
         1 4
            1

и делаем из него треугольную систему уравнений: предпоследний столбец перемещаем в "равно", убираем единичную диагональ, оставшимся столбцам ставим в соответствие коэффициенты a. Получается:

1*a1 1*a2 1*a3 1*a4 = 1
         2*a2 3*a3 4*a4 = 3
                  3*a3 6*a4 = 3
                           4*a4 = 1

Решается снизу вверх простым подставлением: a4 = 1/4, a3 = 1/2, a2 = 1/4, a1 = 0. Для других значений k аналогично.

Вывел этот метод в свое время в школе на волне увлечения олимпиадами (и даже доказал потом задним числом :)). Интересно, что до сих пор не встречал больше никого, кто бы им пользовался.

id_potassium_chloride Jul 23 at 16:34

Кажется, я переоткрыл этот метод минут 10 назад :)

AleksejG Jul 3 at 23:07

Четвертая степень не будет частной производной от первых трех?

AleksejG Jul 3 at 23:17

Но вообще данные поиски необоснованы, так как система счисления с основание 10 не раскрывает все логичечкие степени свобод фрактального числового ряда, необходимого для последующей реализации в ЭВМ.

Naf2000 Jul 4 at 18:28

А где здесь используется система счисления вообще?

de_vligende_golanger Jul 3 at 23:07

Если использовать приём из Конкретной математики, то получается так

tarlex2001 Jul 6 at 01:01

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

Гораздо проще ( на мой взгляд ) всего лишь брать интеграл от предыдущей суммы и получать нужный результат . Соответствующая формула выводится элементарно , если использовать утверждение про суммы производных ( в предыдущих комментариях ) .

de_vligende_golanger Jul 6 at 16:17

А где достать формулу для предыдущей суммы, чтобы взять интеграл? Как уйти от рекуррентности?

tarlex2001 Jul 8 at 11:42

Предыдущая , точнее - самая первая сумма - это сумма нулевых степеней , которая , очевидно равна n . Дальше - интегралом получаем последовательно формулы для любых степеней .

Если подставить в явной форме в формулу для интеграла : Pk(n)=Sum (a(k+1-m)*n^m , 1..k+1) можно получить формулы зависимости коэффициентов следующей суммы от коэффициентов предыдущей . Эту зависимость один из комментаторов показал , но не в общем виде - видимо для наглядности . Правда написал , что коэффициент при первой степени n , надо вычислять ( сумма всех коэффициентов полинома равна 1 ) .

Кстати - этот коэффициент можно не вычислять : это всегда число Бернулли B(k) ...

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

Pk(n)=(1/(k+1))*Sum ( B(m)*C(m,k+1)*n^(k+1-m) ,m=1...k+1 )

здесь C(m,k+1) - биноминальные коэффициенты

wataru Jul 8 at 12:45

Дальше - интегралом получаем последовательно формулы для любых степеней .

Ну так у вас тоже реккурентная формула. Только над полиномами:

$S_n(x) = \int_0^xS_{n-1}(t)dt +xB(n)$

Даже если проигнорировать рекуррентность чисел Бернулли (кстати, если, как я сказал, приравнять Sn(1)=1, то это будет более простое вычисление).

И это, фактически, и есть те самые рекуррентные формулы для коэффициентов, только записанные компактнее.

Ваша "нерекурентная" формула через числа Бернулли напрямую, это уже действительно не рекуррентная формула, но это другая формула, не через интегрирование и вряд ли оно проще для вычисления, ибо тут и биномиальные коээфициенты посчитай, и числа бернулли посчитай, да еще дроби по перемножай.

tarlex2001 Jul 8 at 15:38

Не согласен .

Во первых : рекуррентные формулы , приводимые ранее , требуют знания , а главное - использования всех предыдущих формул для сумм . В " моем " варианте - требуется лишь знание предыдущей суммы и интергал ( приметивнее не бывает...) . Спорить , по моему , невозможно - этот вариант явно проще .

Вычисление " в лоб " через числа Бернули - как вариант , если под рукой есть соответствующая таблица ( чисел Бернули ) , либо соответствующая программа...

В любом случае - рекуррентные формулы - это однозначно , более сложный путь .

А биноминальные коэффициенты посчитать можно даже в ручную и это проще чем суммировать все предыдущие суммы и кстати , тоже с использованием биноминальных коэффициентов .

Я думаю , тут вопрос восприятия : и биноминальные коэффициенты и числа Бернули , можно посчитать самостоятельно и даже вручную , а можно просто " взять " из " таблиц " .

Мой самый первый коммертарий как раз и говорил о том , что " интегральный " способ - наиболее простой и максимально примитивный из всех возможных , для достижения цели и что числа Бернули требуют те же рекуррентные соотношения ( либо разложения в ряд образующей функции ) .

Вы спросили : есть ли " прямая " формула . Я ответил - есть ...

wataru Jul 8 at 15:43

В " моем " варианте - требуется лишь знание предыдущей суммы и интергал

А как вы получите предыдущую сумму, не находя более ранние? Более того, те рекуррентные формулы тоже используют только коэффициенты предыдущей суммы.

что " интегральный " способ - наиболее простой и максимально примитивный из всех возможных

Согласен, он самый удобный, да. Но у вас проблема в терминологии. Он все еще рекуррентный.

tarlex2001 Jul 8 at 16:04

Я и не утверждал , что способ не рекуррентный . Я лишь говорил - он максимально простой , причем во всех смыслах !!!

Есть другое решение ? ! - Буду рад с ним ознакомиться ...

wataru Jul 8 at 17:03

Ну и я, и de_vligende_golanger как-то прочитали в вашем комментарии, что рекуррентные формулы плохо, а вот этот-то метод - не рекуррентный и поэтому хороший.

Вы не немного двояко составили ваш комментарий, если бы вы делали акцент на формулах, а не их рекуррентности, недопонимания бы не было.

tarlex2001 Jul 8 at 15:45

И еще : в " методе через интеграл " не обязательно вводить ( и даже знать ) числа Бернули : сумма всех кожффициентов равна единице - этого достаточно .

Просто " бонус " : можно не вычислять коэффиициент при n , а взать табличный В ( к ) - дело вкуса ( и знаний... )

tarlex2001 Jul 8 at 15:58

И еще вопрос : как вы умудряетесь вводить математическую символику в комментарии - я пытался тупо скопировать из Maple , c соответствующим форматированием - хрень получается . Я что- то не знаю ?

wataru Jul 8 at 17:05

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