5

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.

Unit
  • 7,601
Connie
  • 131
  • The sum on the left hand side has a closed formula (something that depends upon only $n$). Replace the summation with the closed formula and compare the two sides. – Laars Helenius Sep 01 '15 at 00:28
  • https://en.wikipedia.org/wiki/Mathematical_induction

    https://www.khanacademy.org/math/precalculus/seq_induction/proof_by_induction/v/proof-by-induction

     – 9301293 Sep 01 '15 at 00:28
  • 2
    After you have checked it for $n=1$, assume that n is a positive integer with $1^2+\cdots+n^2\ge\frac{n^3}{3}$, and then show that $1^2+\cdots +n^2+(n+1)^2\ge\frac{(n+1)^3}{3}$ – user84413 Sep 01 '15 at 00:29
  • Induction seems to be a bit of overkill if you take the closed formula for the LHS for granted. One uses induction to verify the closed formula, of course. – Laars Helenius Sep 01 '15 at 00:31
  • @LaarsHelenius Induction is certainly not overkill. It is among the simplest methods we have to prove such statements. Also: why would anyone ask this question if one could use the closed formula (read: as a problem in a book)? It is trivial then. – Winther Sep 01 '15 at 00:35

6 Answers6

6

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$.

Bamboo
  • 2,285
4

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}.$$

ncmathsadist
  • 49,383
  • 1
    not "the" Riemann sum but "an", unless you mean an equipartition. Otherwise an excellent answer! – Unit Sep 01 '15 at 01:12
3

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).

Ud779
  • 409
2

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.

Jack D'Aurizio
  • 353,855
2

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.

marty cohen
  • 107,799
1

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.

Amy
  • 13