Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
$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

4 Answers 4

up vote 1 down vote accepted

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

share|improve this answer
    
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$.

share|improve this answer
    
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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.