Давайте сразу обобщим задачу до нахождения \(f_k\left( n \right)\), где

$$f_k\left( n \right) = 1^k + 2^k + \ldots + n^k$$

Для \(k=1\) формула известна всем школьникам: \(f_1\left( n \right) = \frac{n\left(n+1 \right)}{2}\). Формулу для \(k=2\) знают уже не все, но всё же в школе её найти можно (я видел на обложке учебника по алгебре): \(f_2\left( n \right) = \frac{n\left(n+1 \right) \left( 2n + 1 \right)}{6}\)

Интуиция может подсказать, что \(f_k \left( n \right)\) есть некий полином со степенью \(k+1\). Если это так, то его нахождение тривиально. Например, можно посчитать его в явном виде, используя полином Лагранжа. Осталось показать, что наша функция представима в таком виде.

Для начала введём обозначение. “Нижней степенью”, \(x^{\underline{k}}\), будем обозначать такое выражение:

$$x^{\underline{k}} = x(x-1)\cdot \ldots \cdot (x-k+1)$$

.

Далее, заметим следующее, если \(a_i = A_{i+1} - A_i\), где \(\lbrace a_i \rbrace\) и \(\lbrace A_i \rbrace\) — некие последовательности, то \(\sum_{i=1}^n = A_{n+1}-A_1\) (телескопирование, можно посмотреть тут, с. 6).

Теперь посчитаем сумму \(\sum_{i=1}^n i^{\underline{k}}\). Для этого достаточно понять, что \(\left( x+1 \right)^{\underline{k+1}} - \left(x \right)^{\underline{k+1}} = \left( k+ 1 \right)x^{\underline{k}}\). Отсюда сразу получаем, что

$$\sum_{i=1}^n i^{\underline{k}} = \frac{\left( n+1 \right)^{\underline{k+1}}}{k+1}$$

Осталось показать, что “нормальные” степени выражаются через нижние. Начнём со степени \(k=1\), тут всё просто:

$$x = x^{\underline{1}}$$

С бОльшими степенями сделаем следующее: считая, что все степени, меньше, чем \(k\) мы выражать умеем, раскроем скобки в определении нижней степени. Теперь поймём, что старший коэффициент \(1\): \(x^{\underline{k}} = x^k + \sum_{i=1}^k a_ix^i\) или \(x^k = \sum_{i=1}^k a_ix^i - x^{\underline{k}}\). Осталось понять, что каждое из слагаемых вида \(a_ix^i\) мы умеем выражать через нижние степени. Таким образом, можно получить следующее:

$$ \sum_{i=1}^{n} i^k = \sum_{i=1}^{n} \sum_{j=1}^{k} a_j i^{\underline{k}} = \sum_{j=1}^{k} \sum_{i=1}^{n} a_j i^{\underline{k}} = \sum_{j=1}^{k} \frac{a_j \left(n+1 \right)^{\underline{k+1}}}{k+1}$$

Кстати, формула для суммы в самом начале такая:

$$ \sum_{i=1}^n i^5 = \frac{1}{12} n^2 \left(n+1 \right)^2 \left(2n^2 + 2n-1 \right) $$