Суммирование степеней чисел натурального ряда

Требуется вычислить сумму

$S_k=1^k+2^k+....+n^k$

Рассмотрим разность $(m+1)^{k+1}-m^{k+1}=C_{k+1}^1m^k+C_{k+1}^2m^{k-1}+.....+1$

Полагая последовательность $m=0,1,2,....n$ получим равенства:

$1^{k+1}=1$

$2^{k+1}-1^{k+1}=C_{k+1}^11^k+C_{k+1}^21^{k-1}+.....+1$

$2^{k+1}-1^{k+1}=C_{k+1}^12^k+C_{k+1}^22^{k-1}+.....+1$

$.......$

$(n+1)^{k+1}-n^{k+1}=C_{k+1}^1n^k+C_{k+1}^2n^{k-1}+.....+1$

Сложив почленно эти равенства получим

$(n+1)^{k+1}=C_{k+1}^1S_k+C_{k+1}^2S_{k-1}+.....+n+1$

Эта рекуррентная формула позволяет вычислить сумму $S_k$ , если известны предыдущие суммы \( S_1, S_2,....,S_{k-1}

Предположив что $k=1$ получаем

$(n+1)^2=2S_1+n+1$

Отсюда следует что

$S_1=1+2+3+4+5+....+n=\frac{n(n+1)}{2}$

Предположив что $k=2$ получаем:

$(n+1)^3=3S_2+3S_1+n+1=3S_2+3\frac{n(n+1)}{2}+n+1$

Таким способом мы можем высчитывать и суммы и при более высоких значениях