Suponhamos agora que \(\sum_{k=1}^n k^p\) seja um polinômio de grau \(p+1\) em \(n\text{,}\) para todo \(p\in \{1, 2, \ldots, s\}\text{,}\) Mostraremos que essa afirmação é verdadeira para \(p=s+1\text{,}\) isto é, mostraremos que \(\sum_{k=1}^n k^{s+1}\) é um polinômio de grau \(s+2\) em \(n\text{.}\) Observe que
\begin{equation*}
(k+1)^{s+2}=k^{s+2}+(s+2)k^{s+1}+\cdots,
\end{equation*}
onde os termos que não foram escritos explicitamente formam um polinômio de grau \(s\) em \(k\text{.}\) Temos então,
\begin{equation*}
\sum_{k=1}^n (k+1)^{s+2} = \sum_{k=1}^n k^{s+2}+(s+2)\sum_{k=1}^n k^{s+1}+F(n),
\end{equation*}
na qual, \(F(n)\) é um polinômio de grau \(s+1\) em \(n\text{,}\) pela hipótese de indução. Simplificando os termos comuns aos dois primeiros somatórios, obtemos
\begin{equation*}
(n+1)^{s+2} = 1+(s+2)\sum_{k=1}^n k^{s+1}+F(n).
\end{equation*}
Daí,
\begin{equation*}
\sum_{k=1}^n k^{s+1}=\frac{(n+1)^{s+2}-1-F(n)}{s+2}
\end{equation*}
que é um polinômio de grau \(s+2\) em \(n\text{.}\)