Вычислить сумму квадратов первых 7 натуральных чисел

Уроки программирования, алгоритмы, статьи, исходники, примеры программ и полезные советы

ОСТОРОЖНО МОШЕННИКИ! В последнее время в социальных сетях участились случаи предложения помощи в написании программ от лиц, прикрывающихся сайтом vscode.ru. Мы никогда не пишем первыми и не размещаем никакие материалы в посторонних группах ВК. Для связи с нами используйте исключительно эти контакты: vscoderu@yandex.ru, https://vk.com/vscode

Вычисление суммы квадратов чисел

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

Задача поиска суммы квадратов чисел – это классический пример упражнения для закрепления школьниками или студентами раздела программирования Циклы.

Условие задачи: Найти сумму квадратов первых N натуральных чисел.

Рассмотрим два различных способа (алгоритма) решения.

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

Первый и самый очевидный способ решения – суммирование в отдельную переменную квадратов числа i в цикле от i = 1 до N.

Приведем алгоритм вычисления суммы квадратов первых N натуральных чисел на псевдокоде:

Поясним код. Сначала объявляется переменная sum = 0 (строка 2) – в неё мы будем суммировать вычисленные квадраты натурального числа i. Затем в цикле for от 1 до N (строки 3-7) производится вычисление квадрата числа i и сохранение вычисленного результата в переменную j (строка 5), а после j прибавляется к sum (строка 6). В конце, когда все итерации цикла for будут выполнены – вычисление суммы будет завершено. Результат можно вывести на экран (строка 8) или сохранить для дальнейшего использования.

Ниже представлена реализация алгоритма, написанного на псевдокоде. Данный код вы можете использовать при программировании на языках C (Си), C++, C#, Java. Всё будет работать.

Задача

Еще в древнем Египте была известна формула для суммы последовательных натуральных чисел:

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

Найдите формулу для суммы а) квадратов (1^2+2^2+ldots+n^2); б) кубов (1^3+2^3+ldots+n^3); в) четвертых степеней (1^4+2^4+ldots+n^4).

Подсказка 1

Начните c эксперимента: вычислите первые несколько сумм ((1^2+2^2), (1^2+2^2+3^2) и т. д. хотя бы до (n=5)). После этого попробуйте найти закономерность.

Подсказка 2

Экспериментальные данные полезно записать в виде таблицы:

Попробуйте найти связь между числами в (одном столбце, но) разных строках.

Подсказка 3

Если у чисел в двух строках постоянно появляются общие делители (например, 10 и 30 делятся на 10, 15 и 55 — на 5, 28 и 91 — на 7 и т. д.), то полезно изучить отношение этих чисел. Что за последовательности получаются? (Удобно добавить в таблицу из второй подсказки соответствующие строки.)

Решение

Как и предлагалось в последней подсказке, изучим отношение первых двух строк.

Теперь нетрудно заметить закономерность: с увеличением (n) на 1 частное увеличивается на (2/3), то есть это частное равно ((2n+1)/3). Вместе с формулой для суммы (1+2+ldots+n) это дает (гипотетический) ответ

С суммами кубов дело обстоит даже проще, чем с квадратами — глядя на таблицу естественно предположить, что (S_3=S_1^2), то есть

Заметно сложнее угадать формулу для суммы четвертых степеней. В отличие от предыдущих случаев, у (S_4(n)) практически не видно общих делителей с (S_1(n)) (кроме двойки). Зато можно заметить, что 14 и 98 делятся на 7, 55 и 979 — на 14. Посмотрим на отношение (S_4/S_2):

Видно, что после домножения этого отношения на 5 получится последовательность целых чисел: 5, 17, 35, 59, 89, 125. Тут уже нельзя сказать, что разность соседних чисел неизменна. Но если выписать эти разности: 12, 18, 24, 30. то закономерность сразу становится видной!

Таким образом, гипотеза состоит в том, что

Итак, стало понятно, какие должны быть ответы, но как их доказать?

И что вообще значит, что какое-то выражение (P(n)) дает формулу для суммы (1^2+ldots+n^2)?

Это значит, что (P(1)=1), (P(2)=P(1)+2^2), . (P(n)=P(n-1)+n^2). То есть все сводится к быть может утомительному, но прямолинейному вычислению:

Аналогичным образом (говоря формально — по индукции) можно доказать найденные выше формулы для (S_3(n)) и (S_4(n)).

Послесловие

Геометрическое доказательство формулы для суммы (1+2+ldots+n)

Видимо наиболее наглядный способ вычислить сумму (1+2+ldots+n) — геометрический: об этой сумме можно думать как о треугольном числе, то есть площади «пиксельного» (составленного из единичных квадратиков) равнобедренного прямоугольного «треугольника» со стороной (n). Из двух таких треугольников легко составить прямоугольник размера (n imes(n+1)), откуда и получается ответ (n(n+1)/2) (половина площади прямоугольника).

Пирамидка, составленная из квадратов со стороной (1), (2), …, (n)

Подобным образом можно вычислить и сумму (1^2+2^2+ldots+n^2): ее можно проинтерпретировать как объем пирамиды из кубиков (нижний слой которой состоит из (n^2) кубиков, следующий — из ((n-1)^2) кубиков и т. д.), после чего сложить из шести таких пирамид параллелепипед (n imes(n+1) imes(2n+1)). Как это сделать, можно посмотреть на сайте «Математические этюды».

Есть геометрические доказательства и у позволяющего вычислить сумму кубов замечательного равенства (1^3+2^3+ldots+n^3=(1+2+ldots+n)^2). Одно из них можно посмотреть на youtube-канале Think Twice, см. также подборку «доказательств без слов» в «Кванте» №11 за 2017 год.

Заметим, однако, что формула для суммы четвертых степеней не раскладывается (в отличие от предыдущих) на простые линейные множители. Видимо из-за этого ее не получается найти методами геометрического суммирования и открыта она была примерно на 1000 лет позже, чем формула для суммы кубов (известная уже в античности).

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

Практически сразу возникает гипотеза, что вообще для любого (k) сумма (1^k+2^k+ldots+n^k) равна многочлену от (n), который начинается с (frac1n^) (в этом выражении изучавшие математический анализ сразу узнают первообразную того, что мы суммируем), дальше идет (frac12n^k) и члены еще меньших степеней.

С алгебраической точки зрения это очень естественный переход — но самого языка алгебры, «выражений с буквами» и преобразования таких выражений, не существовало до работ Франсуа Виета (конца XVI века)! А до появления такого языка описанную выше гипотезу практически невозможно не то что доказать — сформулировать.

В первой половине XVII века Иоганн Фаульхабер смог найти формулы для сумм (1^k+2^k+ldots+n^k) до (k=17) (интересную попытку реконструкции рассуждений Фаульхабера опубликовал Дональд Кнут). Вот несколько из таких формул:

Коэффициенты при (n^) и при (n^) обсуждались выше. Подумав некоторое время вы наверняка угадаете формулу для коэффициентов при (n^) и (n^), а быть может, — и для коэффициента при (n^).

Возникает надежда на общую (работающую для произвольного (k)) формулу для (S_k(n)). И такую формулу нашел в конце XVII века Якоб Бернулли. В нее входит последовательность так называемых чисел Бернулли ((B^0=1), (B^1=1/2), (B^2=1/6), . ), а саму формулу можно записать символически очень коротко:

Понимать эту запись следует следующим образом. Нужно раскрыть формально в выражении ((n+B)^) скобки, после чего начать воспринимать (B^m) не как степень переменной (B), а как (m)-е число Бернулли. Например:

Если поверить в эту (крайне странную, на первый взгляд) процедуру, то будет ясно и как вычислять числа Бернулли: при подстановке (n=1) получается равенство (1=frac<(1+B)^-B^>), позволяющее найти (B^k), если числа Бернулли с меньшими номерами уже известны. В таблице ниже приведены несколько первых чисел Бернулли.

Замечательным образом те же самые числа Бернулли возникают и в квадратурных формулах для вычисления приближенных значений интегралов, и при вычислении бесконечных сумм типа (1+frac14+frac19+frac1<16>+ldots=frac<pi^2>6) (то есть значений знаменитой дзета-функции), и в комбинаторике, и в теории чисел, и в топологии.

Литература по теме:
1) Д. Пойа. Математика и правдоподобные рассуждения (М.: Наука, 1975). — Мало где можно прочитать не о конкретной области математики, а о том, как вообще решать новую для себя математическую задачу. Подсказки и решение выше по существу следуют главе 7 этой замечательной книги.
2) Интервью с академиком И. М. Гельфандом // Квант, 1989, № 1, стр. 3–12. — В приведенном выше решении сделана попытка объяснить, как некоторые формулы для сумм степеней мог бы искать любой человек. Интересующимся математикой может быть интересно прочитать, как такую задачу решал в школьные годы один из выдающихся математиков XX века (собственно про это — небольшой фрагмент на стр. 8–9, но все интервью интересное).
3) В. С. Абрамович. Суммы одинаковых степеней натуральных чисел // Квант, 1973, № 5, стр. 22–25. — Можно прочитать доказательство формулы для суммы степеней (из конца послесловия), использующее, по сути, только бином Ньютона.
4) Г. А. Мерзон. Алгебра, геометрия и анализ сумм степеней последовательных чисел // Математическое просвещение, сер. 3, вып. 21 (2017), стр. 104–118. — Подробная статья о разных взглядах на задачу о суммировании степеней.
5) Р. Грэхем, Д. Кнут, О. Паташник. Конкретная математика (М.: Мир, 1998). — В учебнике, написанном по лекциям знаменитого Дональда Кнута, обсуждается и задача о суммировании степеней, и числа Бернулли.

Сумма членов арифметической прогрессии, в сущности, сводится к суммированию первых натуральных чисел. Уже в древности возник вопрос о суммировании квадратов и других степеней первых натуральных чисел. На одной из глиняных табличек вавилонян (VI в. до н. э.) было обнаружено равенство:
Видимо, это запись общего правила суммирования квадратов:
которое не могло быть записано в виде формулы (за отсутствием алгебраических обозначений) и потому излагалось с помощью конкретного примера. Мы и здесь не знаем, как вавилоняне получили это правило.
Зато доказательство правила для вычисления суммы квадратов имеется у Архимеда, который применяет его в нескольких случаях, в частности, при определении площади спирали. Дело в том, что, чтобы найти площадь витка спирали, Архимед делит ее на секторы и показывает, что каждый сектор спирали по площади лежит между некими меньшим и большим круговыми секторами, причем разность между суммарной площадью больших секторов, с одной стороны, и меньших секторов, с другой, может быть сделана сколь угодно малой при увеличении числа секторов. А в силу того, что расстояние от точки спирали до центра пропорционально углу оборота, радиусы секторов и их дуги пропорциональны углам оборота, а значит, их площади пропорциональны квадратам углов оборота, пропорциональных, в свою очередь, последовательным натуральным числам. Поэтому возникает вопрос, суммарная площадь больших или меньших круговых сегментов пропорциональна сумме квадратов первых последовательных натуральных чисел, и такую сумму Архимеду надо было уметь определить.

Сумму квадратов Архимед находит, как обычно, в геометрических терминах. При переводе на язык современных алгебраических обозначений и с некоторыми сокращениями его доказательство выглядит так.
Начнем с того, что, как мы уже знаем,
откуда

Если мы запишем такие равенства для всех от 1 до и просуммируем их, получится

Сумму четвертых степеней первых чисел получил арабский математик ал-Караджи (X–XI вв.). Он построил квадрат со стороной , а в нем – другой квадрат (примыкающий к углу первого квадрата) со стороной . Разностью этих двух квадратов является гномон, ширина которого , а большая сторона равна . Площадь этого гномона . Если теперь в квадрате со стороной выделить аналогичный гномон шириной , его площадь будет . Продолжая таким образом, в конце концов дойдем до квадрата со стороной 1. Площадь первоначального квадрата со стороной , таким образом, разбилась на гномоны, площади которых равны , и квадрат площади . Таким образом,

Интересную последовательность рассмотрел французский философ-схоласт XIV в. – Н. Орем. Он задался вопросом: чему была бы равна средняя скорость (в тогдашней терминологии средняя «интенсивность», это более общий термин, но нам сейчас достаточно рассмотреть среднюю скорость) на промежутке, равном 2, если этот промежуток разбит на участки, соответствующие убывающей геометрической прогрессии: , а скорость на каждом участке растет в арифметической прогрессии: 1, 2, 3, 4. Для того, чтобы решить этот вопрос, надо вычислить выражение такого вида: Сумму такого ряда Орем представлял в виде площади ступенчатой фигуры, сделанной из стоящих друг на друге прямоугольников, каждый из которых имеет высоту 1, а ширина нижнего 2, вышележащего 1, далее , и т. д. Вся фигура разбита вертикальными линиями на отрезки шириной и т. д.

Эта фигура, по сути, ни что иное, как график скорости: высота в ее самой левой части равна 1, затем 2, затем 3 и т. д. Сумма ряда равна площади всей фигуры, вместе с тем эту площадь можно найти и иначе: площадь нижнего прямоугольника равна 2, более высокого 1, затем и т. д. – мы имеем дело не с чем иным, как с геометрической прогрессией, сумма которой равна 4. Средняя скорость на всем промежутке равна всей площади (4), деленной на длину промежутка (2) – то есть 2, скорости на втором промежутке. Бесконечно убывающая геометрическая прогрессия и ряд, рассмотренный Оремом, имеют конечную сумму. А другие ряды? Ясно, что для того, чтобы сумма бесконечного числа членов ряда равнялась бы конечной величине, нужно, чтобы сами члены ряда стремились бы к нулю, то есть начиная с достаточно большого номера становились бы меньше любой наперед заданной величины. Но этого мало. Бывают, оказываются, последовательности, стремящиеся к нулю, такие, что сумма ряда стремится к бесконечности. Орем первым доказал, что гармонический ряд

Последовательно полагая и т. д. и считая, что площадь многоугольников с возрастанием неограниченно приближается к площади круга, Виет, перемножая равенства вида нашел, что