Q: Proof that the series $1 * 1 + 2 * 2 + 3 * 3 ... n * n$ is $O(n^3)$ Is this summation correct?:
$\sum_{i=1}^{n} (i \cdot i)$
How would I go about proving that the statement is $O(n^3)$? 

A: Because it's $$\frac{n(n+1)(2n+1)}{6},$$ which we can get by the telescopic sum.

A: Given that you only need $O(n^3)$, a possible answer would be that
$$
\sum_{i=1}^n i^2 \leq \sum_{i=1}^n n^2 \leq n\times n^2 = n^3.
$$
and
$$
\sum_{i=1}^n i^2\ge\sum_{i=2}^ni(i-1)=\frac13\sum_{i=2}^n[(i+1)i(i-1)-i(i-1)(i-2)]=\frac{n(n^2-1)}3\ge\frac13n^3.
$$
