Задача
NT-B2-M12-P014 Суммы степеней
#14
★★★★☆ Уровень 4 из 5
Для \(k\ge1\) обозначим \(S_k(n)=1^k+2^k+\cdots+n^k\). Докажите, что \(S_k(n)\) является многочленом от \(n\) степени \(k+1\) с рациональными коэффициентами.
1001 Problems in Classical Number Theory (method inspiration) · Задача 23
Просуммируйте равенство \((t+1)^{k+1}-t^{k+1}\).
Докажем индукцией по \(k\). Для \(k=1\) формула известна. По биному Ньютона
\[(t+1)^{k+1}-t^{k+1}=(k+1)t^k+\sum_{j=0}^{k-1}\binom{k+1}{j}t^j.\]
Суммируем по \(t=1,\ldots,n\). Левая часть телескопируется в \((n+1)^{k+1}-1\). Суммы меньших степеней по предположению индукции уже являются многочленами. Поэтому \((k+1)S_k(n)\), а значит и \(S_k(n)\), является многочленом. Старший член получается из \((n+1)^{k+1}/(k+1)\), степень равна \(k+1\).
Источник идеи используется как метод конечных разностей, без копирования формулировки.