Prove that $1^{k} + 2^{k} + \cdots + n^{k}$ is $O (n^{k+1})$

Question

I have the following to prove:

$1^{k} + 2^{k} + \cdots + n^{k} \text{ is }O (n^{k+1})$

I have done the following:

$$\frac {1^{k} + 2^{k} + \cdots + n^{k}}{n^k} \leq n$$

Am I on the right track? I don't know how to proceed further and would appreciate some feedback/help.

Thanks!

Answer 1

Hint Use Stolz Cezaro for $$a_n=\frac{1^k+2^k+..+n^k}{n^{k+1}}$$

Answer 2

$$0\leqslant1^k+2^k+\cdots+n^k\leqslant n^k+n^k+\cdots+n^k=n^{k+1}\in O(n^{k+1})$$

Edit:

Exercise: Use the same idea to show the stronger result that $1^k+2^k+\cdots+n^k\in\Theta(n^{k+1})$.

A starting point could be to note that, for every $i$ between $\frac12n$ and $n$, $i^k\geqslant\frac1{2^k}n^k$. There are $\frac12n$ such terms hence $$1^k+2^k+\cdots+n^k\geqslant\frac12n\cdot\frac1{2^k}n^k=\frac1{2^{k+1}}n^{k+1}.$$ Naturally, all this is suboptimal as far as explicit constants are concerned but it fully suffices to show that, for every fixed nonnegative $k$, $$1^k+2^k+\cdots+n^k\in\Theta(n^{k+1}).$$

Answer 3

Since $1^k+2^k\dots+n^k=\sum_{j=1}^{k+1} {k+1\brace j}\binom{n}{j}(j-1)!$ and this is a polynomial over $n$ of degree $k+1$ we are done.