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
Math Forum Home || Math Library || Quick Reference || Math Forum Search