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.