# Prove by induction that $1^2+2^2+…+(n-1)^2<n^3/3<1^2+2^2+…+n^2$

In Apostol's «Calculus I» on page 33 there is the following proof by induction:

To prove: $$1^2+2^2+...+(n-1)^2<n^3/3<1^2+2^2+...+n^2$$ Solution:
Consider the leftmost iequality first, and left us refer to this formula as $A(n)$. It is easy to verify this assertion directly for the first few values of n. Thus, for example, when n takes the values 1, 2, 3, the assertion is true. Our object is to prove that $A(n)$ is true for every positive integer n. The procedure is as follows: Assume the assertion has been proved for a particular value of n, say for $n = k$. That is, assume we have proved $$A(k): 1^2+2^2+…+(k-1)^2<\frac{k^3}{3}$$ for a fixed $k\geqslant 1$. Now using this, we shall deduce the corresponding result for $k+1$: $$A(k+1): 1^2+2^2+…+k^2<\frac{(k+1)^3}{3}$$ Start with $A(k)$ and add $k^2$ to both sides. This gives the inequality $$1^2+2^2+…+k^2<\frac{k^3}{3}+k^2$$ To obtain $A(k+1)$ as a consequence of this, it suffices to show that $$\frac{k^3}{3}+k^2<\frac{(k+1)^3}{3}$$

So my question is why does it suffice to to show the last inequality is true to finish the proof by induction? I don't see how is $A(k+1)$ follows from $A(k)$. It is clear to me that $$A(k) + k^2 < A(k+1)$$ But it is unclear why does it make sense in this case.

-
$A(k)$ is not a formula, it is the entire statement. So $A(k)+k^2<A(k+1)$ is not meaningful. $A(k)$ is the statement of the inequality, not the formula for one side or the other of the inequality. – Thomas Andrews Jun 4 '13 at 17:05
So how do I make sense of proof by induction? To prove by induction I have to show that $A(k+1)$ follows from $A(k)$. What is the procedure in this case? – Fazzolini Jun 4 '13 at 17:14

You know $A(k)$:$$1^2+2^2+\dots+(k-1)^2 < k^3/3$$.

Add $k^2$ to both sides and you know:

$$1^2+2^2+\dots+k^2 < k^3/3 + k^2$$

If you know that $k^3/3+k^2 < (k+1)^3/3$, the you know $A(k+1)$ since:

$$1^2+2^2+\dots+k^2 < (k+1)^3/3$$

-
Now everything makes sense. We showed that whenever $A(k)$ is true, $A(k+1)$ is always true. Thank you. – Fazzolini Jun 4 '13 at 17:27
Actually, it is not very different from the text you quoted, is it? – Hagen von Eitzen Jun 4 '13 at 17:28
@Fazzolini you have to prove A(k+1) is true.here he written that If you know then result is obvious. – Siddhant Trivedi Jun 4 '13 at 17:29
@HagenvonEitzen I was stuck on step $\frac{k^3}{3}+k^2<\frac{(k+1)^3}{3}$ because I was not thinking of $A(k)$ as being a true expression. – Fazzolini Jun 4 '13 at 17:34

If $a<b$ and $b\le c$, then $a<c$.

-
So how do I make sense of proof by induction? To prove by induction I have to show that $A(k+1)$ follows from $A(k)$. What is the procedure in this case? – Fazzolini Jun 4 '13 at 17:11
Now I understand. $A(k)$ implies $a<b$, then it is clear that $A(k+1)$: $a<c$ is true because $b<c$. – Fazzolini Jun 4 '13 at 17:31

\begin{align*} 1^2+2^2+.....+(k-1)^2+k^2 &<\frac{k^3}{3}+k^2(\because A(k)\ \ \text{is true})\\ &=\frac{k^3+3k^2+3k+1}{3}-\frac{3k+1}{3}\\ &<\frac{(k+1)^3}{3} \end{align*}

Therefore the result is true for A($k+1$) if A($k$) is true.

-

Probably easier but a bit too straightforward and slow. For the left inequality add $n^2$ on both sides. LHS becomes $$LHS=\frac{n^3}{3}+\frac{n^2}{2}+\frac{n}{6}$$ and RHS is $$RHS=\frac{n^3}{3}+n^2$$ After all cancellations you get $LHS=n, \ RHS=3n^2$. For the second inequality, add $(n+1)^2$ on both sides. On the RHS after a bit of algebra you get $$\frac{n^3}{6}+\frac{n^2}{2}+\frac{n}{6}+n^2+2n+1$$ After all cancellations you get $0$ on LHS and $\frac{n^2}{6}+\frac{n}{6}$ on RHS, hence both inequalities are proven. Whether this is strict inductive proof, I'm not too sure, more like perturbation method in Concrete Mathematics

-