# Proving $\sum\limits_{i=1}^n i^2$ is $O(n^3)$

Just starting my Data Structures class, and this is one of several questions for my HW in one question. (I.e. this is 1a, but there's b-f too). I have no clue where to even start, the book doesn't lend any hints, it doesn't even explain how to use the sigma notation in this context (I know what sigma is), and my teacher barely speaks English. So can somebody please help me figure out what I'm supposed to do when the book asks the question:

Prove $\sum\limits_{i=1}^n i^2$ is $O(n^3)$ and more generally, $\sum\limits_{i=1}^n i^k$ is $O(n^{k+1})$.

Any help is appreciated. Thanks.

$\sum\limits_{i=1}^n i^k = 1^k + 2^k + \cdots + n^k \le n^k + n^k \cdots + n^k = n(n^k) = n^{k+1} \implies \sum\limits_{i = 1}^n i^k = O(n^{k+1})$.
Note, if the question asked about proving $\sum\limits_{i = 1}^n i^k = \Theta(n^{k+1})$, then this proof won't work.
• You can use this question that I asked recently to prove that it is in $\Theta(n^{k+1})$. – taninamdar Oct 1 '14 at 11:04