The USSR Olympiad Problem Book
#316. (a) Prove that the sum \(1^k + 2^k + 3^k + \cdots + n^k\) is a polynomial in \(n\) of degree \(k+1\).
(b) Calculate the coefficients of \(n^{k+1}\) and \(n^k\) of this polynomial.
Hint. To calculate \(1^2 + 2^2 + 3^2 + \cdots + n^2\), start with this:
\begin{align*}
(n+1)^3 - n^3 &= 3n^2 + 3n + 1\\
n^3 - (n-1)^3 &= 3(n-1)^2 + 3(n-1) + 1\\
(n-1)^3 - (n-2)^3 &= 3(n-2)^2 + 3(n-2) + 1\\
\vdots\\
2^3 - 1^3 &= 3 \cdot 1^2 + 3 \cdot 1 + 1\\
1^3 - 0^3 &= 0^2 + 3 \cdot 0 + 1
\end{align*}
The left side telescopes and the right side contains \(1^2 + 2^2 + 3^2 + \cdots + n^2\) and \(1 + 2 + 3 + \cdots + n\),
enabling the former to be calculated from the latter. They all go like this.