Elementary proof of polynomial degree of sum of pth powers Is there an elementary (ie high school level) proof for the fact that the sum of the first n pth powers is expressible as a polynomial of degree p+1? This is a weaker result than Faulhaber's formula, which can be proved using exponential generating functions.
 A: The most elementary argument that comes to mind can be explained at that level, but it will take a lot of work to do so; in particular, it requires induction. Start with the observation that
$$\begin{align*}
\sum_{k=0}^nk^{m+1}+(n+1)^{m+1}&=\sum_{k=1}^{n+1}k^{m+1}\\
&=\sum_{k=0}^n(k+1)^{m+1}\\
&=\sum_{k=0}^n(k^{m+1}+\text{lower order terms})\\
&=\sum_{k=0}^nk^{m+1}+\sum_{k=0}^n\sum_{i=0}^ma_ik^i\;,
\end{align*}$$
for some coefficients $a_i$. (If you’ve done the binomial theorem, the $a_i$ can be made explicit.) Thus,
$$(n+1)^{m+1}=\sum_{k=0}^n\sum_{i=0}^ma_ik^i=\sum_{i=0}^ma_i\sum_{k=0}^nk^i=\sum_{k=0}^nk^m+\sum_{i=0}^{m-1}\sum_{k=0}^nk^i\;.\tag{1}$$
If we know that $\sum_{k=0}^nk^i$ is a polynomial in $n$ of degree $i+1$ for $i<m$, the last term of $(1)$ is a polynomial in $n$ of degree at most $m$, so
$$\sum_{k=0}^nk^m=(n+1)^{m+1}-\sum_{i=0}^{m-1}\sum_{k=0}^nk^i$$
is a polynomial in $n$ of degree $m+1$. The result now follows by induction.
At worst one can illustrate the technique for the first few exponents; at that point it’s fairly clear that it can be extended indefinitely to higher powers.
