Problem
NT-B2-M12-P014 Sums of Powers
#14
★★★★☆ Level 4 of 5
For \(k\ge1\), let \(S_k(n)=1^k+2^k+\cdots+n^k\). Prove that \(S_k(n)\) is a polynomial in \(n\) of degree \(k+1\) with rational coefficients.
1001 Problems in Classical Number Theory (method inspiration) · Problem 23
Sum the identity \((t+1)^{k+1}-t^{k+1}\).
We prove this by induction on \(k\). For \(k=1\), the formula is known. By the binomial theorem,
\[(t+1)^{k+1}-t^{k+1}=(k+1)t^k+\sum_{j=0}^{k-1}\binom{k+1}{j}t^j.\]
Sum over \(t=1,\ldots,n\). The left side telescopes to \((n+1)^{k+1}-1\). By the induction hypothesis, sums of lower powers are already polynomials. Therefore \((k+1)S_k(n)\), and hence \(S_k(n)\), is a polynomial. Its leading term comes from \((n+1)^{k+1}/(k+1)\), so the degree is \(k+1\).
The source idea is used as a finite-difference method, without copying the wording.