Prove a lower bound for $\sum_{i=1}^n i^2$ 
Prove that $$\sum_{i=1}^n i^2 \geq \frac{n^3}{3}$$ for all $n \geq 1.$

What I know: I know the basic format of how to make a proof with the basis and inductive step but I am unsure of how to prove this particular statement and expand it. This is for a data structures class by the way.
My attempt so far has been $1^2 + 2^2 +\cdots+n^2$ is $i^2$ expanded. Can anyone provide some insight or link me to similar examples on how to go about structuring this? 
Thanks so much in advance I am really lost and haven't taken a proofs class before so it's all new to me.
 A: Since it sounds like you want to do this using induction (there are easier ways since, as people mentioned, there is a closed formula for your sum), here's a detailed example.  (Of course, you would establish the closed formula people are suggesting by induction anyway, usually.)
For the base case, you have $n=1$.  On the left
$$ \sum_{i=1}^n i^2 = \sum_{i=1}^1 i^2 = 1. $$
On the right,
$$ \frac{n^3}{3} = \frac{1}{3}.  $$
So, indeed your inequality holds for the case $n=1$.
Assume then that the inequality holds for some positive integer $k$, i.e., assume,
$$ \sum_{i=1}^k i^2 \geq \frac{k^3}{3}.  $$
Now, we want to show that if we assume this fact, then the inequality will hold for $k+1$ as well.  So, examine the $k+1$ case and try to use our inductive hypothesis:
\begin{align*}
 \sum_{i=1}^{k+1} i^2 &= \left( \sum_{i=1}^k i^2 \right) + (k+1)^2 &(\text{Pulling term out of sum}) \\
 &\geq \frac{k^3}{3} + (k+1)^2 &(\text{Ind. Hyp}) \\
 &= \frac{k^3 + 3k^2 + 6k + 3}{3} &(\text{Common denominator}) \\
 &\geq \frac{k^3 + 3k^2 + 3k + 1}{3} &(\text{Taking away some positive terms})\\
 &= \frac{(k+1)^3}{3}.
\end{align*}
This is the inequality you wanted.  So, if the statement is true for $k \in \mathbb{Z}_{\geq 0}$ then it is true for $k+1$ as well.  Since we already showed it is true for $n=1$, we have that it is true for all positive integers $n$.
A: The sum
$$\sum_{k=1}^n k^2$$
is the upper Riemann sum for the integral
$$\int_0^n x^2\, dx$$
for a partition with $n$ equal-sized intervals. Therefore
$$\sum_{k=1}^n k^2 \ge \int_0^n x^2\, dx = {n^3\over 3}.$$
A: The left hand side of your equation can be simplified to 
$\frac{1}{6}n(n+1)(2n+1) = \frac{n^3}{3}+\frac{n^2}{2}+\frac{n}{6}$. Substituting this in, you just have to prove that $\frac{n^2}{2}+\frac{n}{6} \geq 0$, which is true for any positive integer $n$ (or positive real number).
A: It is enough to prove that, for any $n\geq 1$:
$$n^2+2n+1=(n+1)^2\color{red}{\geq} \frac{(n+1)^3-n^3}{3} = \frac{3n^2+3n+1}{3} = n^2+n+\frac{1}{3}$$
that is quite trivial.
A: Here's another way to look at it.
Suppose you guess that
$s(n)
=\sum_{i=1}^n i^2$
grows something like $n^3$.
You conjecture that
$s(n)
\ge cn^3$
for some positive $c$.
For $n=1$,
this becomes
$1 \ge c$,
so the induction base case
holds for any $c \le 1$.
Suppose this holds for $n$,
so that
$s(n) \ge c n^3$.
You now want to show that
this holds for
$n+1$,
so that $s(n+1) \ge c(n+1)^3$.
Since $s(n+1)
= s(n)+(n+1)^2$,
we need to 
find a value of $c$
such that
$s(n) \ge cn^3$
implies that
$s(n+1) \ge c(n+1)^3
$.
The basic identities needed
are that
$s(n+1)-s(n)
=(n+1)^2
$
and
$(n+1)^3-n^3
=3n^2+3n+1
$.
Since we want
$s(n+1)
\ge c(n+1)^3
$,
using the identities,
this is the same as
$s(n)+(n+1)^2
\ge c(n^3+3n^2+3n+1)
$.
Since we are assuming that
$s(n) \ge cn^3
$,
this is implied by
$cn^3+(n+1)^2
\ge c(n^3+3n^2+3n+1)
$,
or
$n^2+2n+1
\ge 
c(3n^2+3n+1)
$
or
$n^2(1-3c)+n(2-3c)+(1-c)
\ge 
0
$.
The easiest way to have this happen
is to have all those
coefficients $\ge 0$.
It turns out that
$c=\frac13$ is the largest value
that works for all three.
Therefore,
we have shown that
if 
$s(n) \ge \frac{n^3}{3}$,
then
$s(n+1) \ge \frac{(n+1)^3}{3}
$.
Finally,
since
$s(1) 
\ge \frac13
$,
$s(n)
\ge \frac{n^3}{3}
$ holds for all $n$
and we are done.
A: You could also view this geometrically.  If you have a cube with sides of length $n$, then the volume of the pyramid with the same base is 
$$V = \frac{n^3}{3}.$$  
However, this pyramid is stricly smaller than stacking squares with sides $n, n-1, \ldots, 1$ since this is precisely as high as the pyramid, but at each level the squares stick out from the pyramid.
