# Big O — mathematical Proof with a summation series

I am looking to prove that for every fixed value of $k$, $$n^{k+1}= O(1^k + 2^k + \cdots + n^k)$$

I have already proved that $1^k + 2^k +\cdots + n^k =O(n^{k+1})$ but I don't know how to make the jump to proving the opposite is true. I was thinking that induction might be the way to go (i.e. adding $(n+1)^k$ to each side and simplifying, but the way I did it didn't make anything obvious).

Any help will be very much appreciated.

Thanks, Nolan

-
Can you please define precisely $f=O(g)$? I think you are using a non-standard definition. The standard one says that $f=O(g)$ if the quotient $|f/g|$ is bounded from above by a constant. –  Siminore Sep 24 '12 at 8:53

$$n\cdot n^k\geqslant\sum_{i=1}^ni^k\geqslant\sum_{i=1}^n\int_{i-1}^it^k\,\mathrm dt=\int_{0}^nt^k\,\mathrm dt=\frac{n^{k+1}}{k+1}.$$ Hence, indeed $n^{k+1}=O(1^k+2^k+\cdots+n^k)$ when $n\to\infty$, and in fact, $$1^k+2^k+\cdots+n^k=\Theta(n^k).$$
The integral of $t\mapsto t^k$ on $[0,n]$? Well, this is just the value at $n$ minus the value at $0$ of any primitive of $t^k$, for example $t^{k+1}/(k+1)$. The result is that your sum is between $n^{k+1}/(k+1)$ and $n^{k+1}$, hence the asymptotics you are after. –  Did Sep 24 '12 at 9:05
The crucial step is that, for each $i$, $i^k\geqslant t^k$ for every $t$ in $[i-1,i]$ hence $i^k$ is at least the integral of $t^k$ on the interval $[i-1,i]$, divided by the length $1$ of the interval. –  Did Sep 24 '12 at 9:07
Lower bound without integrals: $$\sum_{i=1}^n i^k \ge \sum_{i=\lfloor n/2 \rfloor }^n i^k \ge \frac{n-1}{ 2} \left( \frac{n-1}{ 2} \right)^k =\Omega(n^{k+1})$$