Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Proof by Induction


Date: 7/3/96 at 19:0:59
From: Scott Turner
Subject: Proof by Induction

I'm trying to prove that 1 + 1/4 + 1/9 + ... 1/n^2 < 2 - 1/n for all 
n > 1.

Now the base step is simple: n = 2: 1 + 1/4 < 2 - 1/2, true

The inductive step is assume true for n.  I must show it is also true 
for n + 1 so 1 + 1/4 + 1/9 + .. 1/n^2 + 1/(n+1)^2 < 2 - 1/n+1 which I  
know is < (2 - 1/n) + 1/(n+1)^2 by the inductive hypothesis.  My 
problem is that I end up with an algebraic equation which can't be 
broken down and which I can't assume proves my above assertion.

Help.

St


Date: 7/4/96 at 2:22:32
From: Doctor Pete
Subject: Re: Proof by Induction

The assumption that the statement to be proved is true for some n is 
called the induction hypothesis.  It is not circular reasoning because 
the proof requires that the given is true for *all* n.  The inductive 
step is the part where you show that the truth of the induction 
hypothesis implies that the given statement is also true for the next 
value of n.  This completes the proof.

So in order to work this out, you show the first case (n=2); this was 
done. Then you make the induction hypothesis, which you also have 
done.  Then you start from the induction hypothesis to create the next 
case, n --> n+1, and show this is true.  With this in mind, we have

           1 + 1/4 + 1/9 + ... + 1/n^2 < 2 - 1/n                   [1]
  => 1 + 1/4 + ... + 1/n^2 + 1/(n+1)^2 < 2 - 1/n + 1/(n+1)^2       [2]
                                       = 2 - (1/n - 1/(n+1)^2)
                                       < 2 - (1/n - 1/(n*(n+1)))   [3]
                                       = 2 - (1 - 1/(n+1))/n       [4]
                                       = 2 - ((n+1-1)/(n+1))/n
                                       = 2 - (n/(n+1))/n
                                       = 2 - 1/(n+1).

[1]:  This is the induction hypothesis.
[2]:  Added 1/(n+1)^2 to both sides.
[3]:  Note 1/(n+1)^2 = 1/((n+1)*(n+1)) < 1/(n*(n+1)).
[4]:  Factored out 1/n.

Since we have shown the (n+1)th case is true if the (n)th case is 
true, and the case for n=2 is true, then the given statement is true 
for all n greater than or equal to 2.

I believe that the problem you were running into had more to do with 
finding the appropriate simplification, but it was complicated by the 
fact that when you were working this out, you started from the (n+1)th 
case.  Also, perhaps you were looking for strict equalities to 
transform one case into the next, rather than for a chain of 
inequalities that allow for the right simplifications:  note I used an 
inequality in step [3].

Hope this clears things up.  :)

-Doctor Pete,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/   
    
Associated Topics:
High School Discrete Mathematics
High School Sequences, Series

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/