Proof by induction summation inequality: $\sum_{i=1}^n i^2 = O(n^3)$

Question

show by induction that: $$\sum_{i=1}^n i^2 = O(n^3)$$

what I have so far:

$$\sum_{i=1}^n i^2 \le n^3$$

base case: for n=1 $$\sum_{i=1}^1 i^2 \le 1^3$$ --------------------------------------------------> 1=1 is correct

inductive step: assume true for n=k then for n=k+1

$$\sum_{i=1}^{k+1} i^2 = \sum_{i=1}^{k} i^2 + (k+1)^2 \le k^3 + (k+1)^2$$

$$\le k^3 +(k+1)^2 \le k^3 +(k+1)^2$$

$$...$$ at this point I am not sure where to go to finish off this proof can someone advise?

EDIT solution: $$k^3 + (k+1)^2 = k^3 + k^2 +2k + 1$$
$$(k+1)^3 = k^3 + 3k^2 + 3k + 1$$

$$\sum_{i=1}^{k+1} i^2 \le k^3 + k^2 + 2k +1 <= k^3 + 3k^2 + 3k + 1$$ $$ therefore \sum_{i=1}^{k+1} i^2 \le (k+1)^3$$ ------------------------------------------->statement is true for n=k+1

Answer 1

You are almost done! $$k^3+(k+1)^2=k^3+k^2+2k+1\le k^3+3k^2+3k+1=(k+1)^3$$

Answer 2

Here is a tedious approach.

Suppose, by analogy with integration, that $\sum_{k=1}^n k^2 = a n^3 + b n^2 + c n + d$, then we can solve for $a,b,c,d$ by getting 4 equations in $(a,b,c,d)$ by setting $n=1,2,3,4$. This gives $\begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 2 & 4 & 8 \\ 1 & 3 & 9 & 27 \\ 1 & 4 & 16 & 64 \\ \end{bmatrix} \begin{bmatrix} d \\ c \\ b \\ a\end{bmatrix} = \begin{bmatrix} 1 \\ 5 \\ 14 \\ 30\end{bmatrix} $, and solving gives $(a,b,c,d) = ({1 \over 3}, {1 \over 2}, {1 \over 6}, 0)$.

Now we need use induction to check that $\sum_{k=1}^n k^2 = s_2(n) = {1 \over 3}n^3 +{1 \over 2} n^2+ {1 \over 6}n$. It is true for $n=1$, so suppose it is true for $n$, then $\sum_{k=1}^{n+1} k^2 = {1 \over 3}n^3 +{1 \over 2} n^2+ {1 \over 6}n + (n+1)^2 = {1 \over 3}n^3 +{3 \over 2} n^2+ {13 \over 6}n +1$, computing $s_2(n+1)$ directly gives the same result, hence the result is true of all $n$.