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

Вам наверняка известна история о математике Карле Гауссе. Когда ему было восемь лет, учитель задал его классу посчитать сумму всех натуральных чисел от 1 до 100:

1 + 2 + 3 + 4 + \ldots + 97 +98 + 99 + 100

И пока остальные дети трудились над последовательным сложением, Гаусс нашел простое и изящное решение. Он заметил, что числа можно сгруппировать в 50 пар с одинаковой суммой:

\underbrace{1 + 100}_{101} = \underbrace{2 + 99}_{101} = \underbrace{3+ 98}_{101} =\underbrace{4 + 97}_{101} =\dots=\underbrace{49 + 52}_{101} = \underbrace{50 + 51}_{101}

и мгновенно получил ответ 50\cdot 101 = 5050.

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

В этой статье мы рассмотрим графический метод нахождения формул для суммы степеней натурального ряда

1^k + 2^k + 3^k + \ldots + n^k

для значений k = 1, k = 2, k = 3.

Случай k = 1

Пусть мы ищем формулу для нахождения суммы натуральных чисел от 1 до n:

1 + 2 + 3 + \ldots + n

Изобразим числа в этой сумме соответствующим числом квадратов:

7d854838e759cd07be43105b21a83969.png

Несложно заметить, что количество квадратов в такой фигуре и есть искомая сумма.

Соединим две такие фигуры:

f165d6c7186fc698cbea32e00129f750.png

Получим прямоугольник со сторонами n и n+1. Площадь такого прямоугольника вычисляется по формуле n\cdot (n + 1). Значит, искомая сумма равна половине площади прямоугольника, то есть:

1 + 2 + 3 + \ldots + n = \dfrac{n\cdot (n+1)}{2}

Раскрыв скобки в правой части, полученную формулу можно записать в виде:

1 + 2 + 3 + \ldots + n =  \dfrac{1}{2}n^2+\dfrac12n

Случай k = 2

Пусть мы ищем формулу для нахождения суммы квадратов натуральных чисел от 1 до n:

1^2 + 2^2 + 3^2 + \ldots + n^2

Рассмотрим прямоугольную таблицу размером n на 2n+1, заполненную числами так, как показано на рисунке ниже:

f34997a5e2f848fe86ca861bbf059686.png

Суммы чисел, помеченных зеленым и сиреневым цветами, очевидно равны:

\underbrace{1}_{1 \, число} + \underbrace{2 + 2}_{2 \, числа}+ \underbrace{3 + 3+ 3}_{3 \, числа} +\ldots+\underbrace{n+n+n+\ldots+n}_{n \, чисел} = 1^2+2^2+3^2+\ldots+n^2

Рассмотрим сумму чисел, помеченных желтым цветом.

b5110542dfecec8927a36995aec63f5e.png

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

1 + (1+2+1)+(1+2+3+2+1)+ (1+2+3+4+3+2+1) + \ldots+\\[10pt] + \,(1+2+3+\ldots +n + n-1+n-2+\ldots+1) = \\[10pt]=1+4+9+16+\ldots+n^2 \ = 1^2+2^2+3^2+\ldots+n^2

Таким образом, сумма всех чисел в прямоугольной таблице есть утроенная искомая сумма квадратов:

3\cdot(1^2+2^2+3^2+\ldots+n^2)

С другой стороны, мы имеем 2n + 1 столбцов, в каждом из которых (сверху вниз) записана сумма:

1 + 2 + 3 + \ldots + n = \dfrac{n\cdot (n+1)}{2}

С учетом вышесказанного получаем:

3\cdot(1^2+2^2+3^2+\ldots+n^2) = \dfrac{n\cdot (n+1)}{2}\cdot (2n+1)

Отсюда получаем следующее:

1^2+2^2+3^2+\ldots+n^2 = \dfrac{n\cdot (n+1)\cdot(2n+1)}{6}

Раскрыв скобки в правой части, полученную формулу можно записать в следующем виде:

1^2+2^2+3^2+\ldots+n^2 = \dfrac13n^3+\dfrac12n^2+\dfrac16n

Случай k = 3

Пусть мы ищем формулу для нахождения суммы кубов натуральных чисел от 1 до n:

1^3 + 2^3 + 3^3 + \ldots + n^3

Для нахождения такой суммы воспользуемся таблицей Пифагора. Таблица Пифагора — это квадратная таблица n\times n, в каждой ячейке которой записано число, равное произведению номеров своих строки и столбца. По сути, это обычная таблица умножения.

d7b3ca002345cd53cea2a1fbc30e3b41.png

Рассмотрим суммы чисел, помеченных одинаковым цветом:

1 = 1^3\\[10pt]2+4+2 = 2^3\\[10pt]3+6+9+6+3 = 3^3\\[10pt]4+8+12+16+12+8+4 = 4^3\\[10pt]5+10+15+20+25+20+15+10+5 = 5^3\\[10pt] \ldots \\[10pt] n+2n+3n+\ldots+n^2+n(n-1)+n(n-2)+\ldots+3n + 2n +n=n^3

Таким образом, сумма всех чисел в таблице Пифагора равна:

1^3+2^3+3^3+\ldots + n^3

С другой стороны, сумма чисел в таблице Пифагора равна:

\underbrace{1+2+3+\ldots + n}_{1 \, строка \, таблицы} +  \underbrace{2 + 4 + 6+\ldots+2n}_{2\, строка\, таблицы} +\ldots+ \underbrace{n+2n+3n+\ldots+n^2}_{n \, строка \, таблицы} = \\[25pt] = (1+2+3+\ldots + n) +  2(1 + 2 + 3+\ldots+n)+\ldots+ n(1+2+3+\ldots+n) =\\[10pt] = (1+2+3+\ldots+n)\cdot(1+2+3+\ldots+n) = (1+2+3+\ldots + n)^2 = \\[10pt] =\left(\dfrac{n(n+1)}{2}\right)^2=\dfrac{n^2(n+1)^2}{{4}}

Итак, получили формулу:

1^3+2^3+3^3+\ldots+n^3 = \dfrac{n^2(n+1)^2}{4}

Раскрыв скобки в правой части, полученную формулу можно записать в следующем виде:

1^3+2^3+3^3+\ldots+n^3 = \dfrac14n^4+\dfrac12n^3+\dfrac14n^2

Графический метод хорош и нагляден, однако у него есть серьезный недостаток: решения никак не связаны друг с другом и по мере увеличения значения k усложняются. Для нахождения суммы четвертых степеней 1^4+2^2+3^4+\ldots + n^4 придется искать что-то принципиально отличное от всего предыдущего.

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

Заключение

С помощью графических рассуждений нам удалось вывести формулы для нахождения суммы степеней натурального ряда 1^k + 2^k + 3^k + \ldots + n^k при k = 1, k = 2, k= 3:

1 + 2 + 3 + \ldots + n = \dfrac{n\cdot (n+1)}{2} = \dfrac{1}{2}n^2+\dfrac{1}{2}n \\[15pt]  1^2+2^2+3^2+\ldots+n^2 = \dfrac{n\cdot (n+1)\cdot(2n+1)}{6} = \dfrac13n^3+\dfrac12n^2+\dfrac16n \\[15pt]  1^3+2^3+3^3+\ldots+n^3 = \dfrac{n^2(n+1)^2}{4} = \dfrac14n^4+\dfrac12n^3+\dfrac14n^2

Глядя на три данные формулы, можем быстро вывести гипотезу, что для любого натурального значения k сумма 1^k + 2^k + 3^k + \ldots + n^k равна некоторому многочлену от переменной nстепени k + 1, который начинается со слагаемого\dfrac{1}{k+1}n^{k+1}, за которым идет слагаемое \dfrac{1}{2}n^k и члены еще меньших степеней.

Во второй части этой статьи мы подтвердим указанную выше гипотезу и рассмотрим несколько аналитических методов нахождения формул суммы 1^k + 2^k + 3^k + \ldots + n^kдля любых натуральных значений k.

Также хочется отметить, что знание рассмотренных в статье формул оказывается полезным и при решении задач на программирование. Классическая задача с алгоритмического собеседования звучит следующим образом: имеется список целых чисел, в котором каждое из чисел от 1 до n встречается ровно один раз — кроме одного отсутствующего числа. Требуется найти отсутствующее число.

Наиболее быстрое и асимптотически оптимальное решение такой задачи основано на использовании следующей формулы:

1 + 2 + 3 + \ldots + n = \dfrac{n\cdot (n+1)}{2}

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

1^2+2^2+3^2+\ldots+n^2 = \dfrac{n\cdot (n+1)\cdot(2n+1)}{6}

Задачи для самостоятельного решения

Задача 1. Используя графические рассуждения, выведите формулу для нахождения
суммыnпервых нечетных натуральных чисел:

1 + 3 + 5 + 7 + \ldots + 2n-1Подсказка 1

Сопоставьте каждому нечетному числу (1, 3, 5, 7, \ldots) следующую фигуру:

a919e3b123a443ccd17c7611d9218694.png

Подсказка 2

Вкладывая указанные фигуры друг в друга, вы получите квадрат со стороной n, площадь которого равна n^2.

b43c4a88d6c16866c832aede602388d9.png

Задача 2. Как мы уже знаем, таблица Пифагора — это квадратная таблица n\times n, в каждой ячейке которой записано число, равное произведению номеров своих строки и столбца. Ниже представлена таблица Пифагора для n = 6 и n = 9.

d52657a1d805a01668dbb9d30a534b96.png

Для таблицы Пифагора размером n \times nтребуется вывести формулы для нахождения:

  • суммы чисел, расположенных на побочной диагонали (выделена зеленым цветом)    

  • суммы чисел выше и левее побочной диагонали (выделены синим цветом)

  • суммы чисел ниже и правее побочной диагонали (выделены желтым цветом)

Проверить своё решение можно по ссылке.

© Habrahabr.ru