Let $k$ be a positive integer. Prove by induction on $n$ that $$ \sum_{r=1}^n r( r+1) ( r+2) \cdots( r+k-1) =\frac{n( n+1) (n+2) \cdots(n+k)}{k+1} $$ Show now by induction on $k$ that $$ \sum_{r=1}^{n}r^k=\frac{n^{k+1}}{k+1}+E_{k}(n), $$ where $E_{k}(n)$is a polynomial in $n$ of degree at most $k$°
The first part is quite straightforward, and I can derive the final result by telescoping, $$\sum_1^{n-1}(r+1) ^k-r^k $$
But no idea how to derive the result by induction on $k$
Assuming you have no difficulty with the first part (induction on $n$).
For the second part of the question, it is trivial to show the statement is true for $k=1$. Now assume the statement is true for $k \le m$. Then $$\sum_{r=1}^{n}r^k=\frac{n^{k+1}}{k+1}+E_{k}(n),\quad \text{for } k\le m.$$
Now let's look at the the case for $m+1$ by making use of the conclusion of the first part at $m+1$. $$ \sum_{r=1}^n r( r+1) ( r+2) \cdots( r+m) =\frac{n( n+1) (n+2) \cdots(n+m+1)}{m+2}. $$
We expand both sides into individual terms of power of $r$ on the left hand side, and power of $n$ on the right hand side. We got two polynomials of $r$ and $n$, i.e. $$ \sum_{r=1}^n \left( r^{m+1} + a_1r^{m}+\cdots + a_{m}r+a_{m+1} \right) =\frac{n^{m+2} + b_1n^{m+1} \cdots + b_{m+1}n}{m+2}, $$ where $a_i$ and $b_j$ are coefficients from expansion and combining terms of the same degrees. Hence $$ \sum_{r=1}^n r^{m+1} + a_1\sum_{r=1}^n r^{m}+\cdots + a_{m}\sum_{r=1}^n r+\sum_{r=1}^n a_{m+1} =\frac{n^{m+2}}{m+2} + E_{m+1}(n).$$ By applying induction assumptions, we have $$ \sum_{r=1}^n r^{m+1} + a_1\left( \frac{n^{m+1}}{m+1}+E_{m}(n) \right)+\cdots a_{m}\left( \frac{n^{1+1}}{1+1}+E_{1}(n) \right)+ a_{m+1}n =\frac{n^{m+2}}{m+2} + E_{m+1}(n).$$ Note all items of the left hand side except the first one is a polynomial of $n$ with degrees of at most $m+1$. Hence we can write $$ \sum_{r=1}^n r^{m+1} + E_{m+1}^\prime(n) = \frac{n^{m+2}}{m+2} + E_{m+1}(n), $$ where $E_{m+1}^\prime(n)$ is a polynomial of $n$ with degrees of at most $m+1$, and the prime signifies it is different from $E_{m+1}(n)$.
Moving $E_{m+1}^\prime(n)$ to the right hand side and merging it with $E_{m+1}(n)$ leads to $$ \sum_{r=1}^n r^{m+1} = \frac{n^{m+2}}{m+2} + E_{m+1}''(n),$$ where $E_{m+1}''(n)$ is a polynomial of $n$ with degrees of at most $m+1$.
We just finished showing that the statement is true for $k=m+1$. Hence the statement is proved.