I have the following problem and I am stuck on it. Any ideas on how to work it?
Let k be a positive integer. Show that 1^k + 2^k + ... + n^k is O( n^(k+1) )
You want to show that $\displaystyle \frac{\sum_{r=1}^nr^k}{n^{k+1}}$ is bounded as $\displaystyle n\to\infty$. One way is to write that expression as $\displaystyle \frac1n\sum_{r=1}^n\Bigl(\frac rn\Bigr)^k$ and think of it as a Riemann sum approximating $\displaystyle \int_0^1\!\!x^k = \frac1{k+1}$.