In principle you can use induction whenever you’re trying to prove a statement of the form $$P(k)\text{ is true for all integers }k \ge k_0,$$ where $P(k)$ is some assertion about the number $k$. Here the assertion $P(k)$ is a bit complicated: $$\text{for all integers }n\ge 0,\sum_{i=0}^n i^k\text{ is a polynomial in }n\text{ whose leading term is }\frac{n^{k+1}}{k+1}.$$
It is in fact possible to prove this by induction on $k$, though the proof is difficult enough that I’m not at all sure that the question is actually asking you to find it.
Suppose that you know that for every $k, $$\sum_{i=0}^n i^k = \frac{n^{k+1}}{k+1} + p_k(n),$$ where $p_k$ is a polynomial of degree at most $k$. You’d like to use this hypothesis to show that $$\sum_{i=0}^n i^m = \frac{n^{m+1}}{m+1} + p_m(n)$$ for some polynomial $p_m$ of degree at most $m$. The trick is to skip a step and look at $\sum_{i=0}^n i^{m+1}$: $$\begin{align*} \sum_{i=0}^n i^{m+1} + (n+1)^{m+1} &= \sum_{i=0}^n (i+1)^{m+1}\\ &= \sum_{i=0}^n\left(i^{m+1}+(m+1)i^m + q_{m-1}(i) \right)\\ &= \sum_{i=0}^n i^{m+1} + (m+1)\sum_{i=0}^n i^m + \sum_{i=0}^n q_{m-1}(i), \end{align*}$$ where the second step uses the binomial expansion, and $q_{m-1}$ is a polynomial of degree at most $m-1$ containing the remaining terms of that expansion. Subtracting $\sum_{i=0}^n i^{m+1}$ from both sides, we have $$\qquad\qquad(n+1)^{m+1} = (m+1)\sum_{i=0}^n i^m + \sum_{i=0}^n q_{m-1}(i).\qquad\qquad(*)$$ Let $$q_{m-1}(x) = a_0 x^{m-1} + a_1 x_{m-2} + \dots + a_{m-1} = \sum_{j=0}^{m-1}a_{m-1-j} x^j;$$ then $$\begin{align*} \sum_{i=0}^n q_{m-1}(i) &= \sum_{i=0}^n \sum_{j=0}^{m-1} a_{m-1-j} i^j\\ &= \sum_{j=0}^{m-1}\sum_{i=0}^n a_{m-1-j} i^j\\ &= \sum_{j=0}^{m-1} a_{m-1-j} \sum_{i=0}^n i^j\\ &= \sum_{j=0}^{m-1} a_{m-1-j} \left(\frac{n^{j+1}}{j+1} + p_j(n) \right) \end{align*}$$ is a polynomial in $n$ of degree at most $m$, which I’ll call $r_m(n)$.
Substitute this into $(*)$: $\displaystyle(n+1)^{m+1} = (m+1)\sum_{i=0}^n i^m + r_m(n)$, so $$\begin{align*} (m+1)\sum_{i=0}^n i^m &= (n+1)^{m+1} - r_m(n)\\ &= n^{m+1} + s_m(n) - r_m(n), \end{align*}$$ where $s_m$ is a polynomial of degree $m$. Here again I’ve used the binomial theorem. Now $s_m(n) - r_m(n)$ is clearly a polynomial in $n$ of degree at most $m$, so if we set $$p_m(n) = \frac{1}{m+1}(s_m(n) - r_m(n),$$ then $p_m$ is a polynomial of degree at most $m$, and $$\sum_{i=0}^n i^m = \frac{n^{m+1}}{m+1} + p_m(n),$$ as desired.