# Homework Help: Simple inequality proof by induction

1. Mar 28, 2010

### missavvy

Hey guys... I just did this question... and I have the solution but I do not understand it still. If someone could just explain what happened.

1. The problem statement, all variables and given/known data

1 + 1/4 + ... 1/n2 < 2 - 1/n
For n>=2

2. Relevant equations

3. The attempt at a solution
So the base case:
n=2:
1/4 < 2- 1/2, 1/4 < 3/2 True

Suppose this holds for n:

1+ 1/4 +... 1/n2 + 1/(n+1)2 < 2 - 1/n + 1/(n+1)2

Here is where I don't understand what happens..
Since 1/n - 1/(n+1) = 1/n(n+1) > 1/(n+1)2 , we have 2 - 1/n + 1/(n+1)2 < 2 - 1/(n+1).
Then the inequality for n+1 follows.

So I'm confused with why we use 1/n - 1/(n+1).. where did it come from ?
Thanks!

2. Mar 28, 2010

### CompuChip

I color coded that expression for you. We want to look at the expression on the left hand side and show that it is smaller than 2 - 1/(n + 1). The part that I colored in blue, is smaller than the part in blue on the right hand side, by the induction hypothesis. The part in red is just copied over. (It's just using that a + c < b + c, whenever a < b - for a, b, c > 0). Basically, we recognised the induction hypothesis and just literally substituted it.

So you want the entire thing to be less than 2 - 1/(n + 1). Therefore you need to show that 1/n + 1/(n+1)2 < 1/(n + 1).

The way I would show this is as follows:
$$\frac{1}{n} + \frac{1}{(n+1)^2} = \frac{1}{n+1} \left( \frac{n + 1}{n} + \frac{1}{n + 1} \right) = \frac{1}{n + 1} \left( 1 + \frac{1}{n} + \frac{1}{n + 1} \right)$$
and since the last two terms in the brackets are positive, this is definitely smaller than
1/(n + 1).

3. Mar 29, 2010

### missavvy

Thanks for the help.

I still don't understand the part to show 1/n + 1/(n+1)2 < 1/(n + 1). I don't understand where the teal coloured terms are coming from. Did you bring the 1/n over from the right side to the left? What happened to the 2 and why is there a 1/(n+1) still there on the right of the inequality if that is what happened?

Sorry if I'm over complicating things. Perhaps I'm just overanalyzing this..

4. Mar 31, 2010

### CompuChip

Do you understand what we are trying to prove?

We want to show that
1 + 1/4 + ... 1/n2 + 1/(n + 1)2 < 2 - 1/(n + 1), (*)
given that
1 + 1/4 + ... 1/n2 < 2 - 1/n. (**)

So we start on the left hand side, with the expression
1 + 1/4 + ... 1/n2 + 1/(n + 1)2
Let me put a pair of brackets there:
... = ( 1 + 1/4 + ... 1/n2) + 1/(n + 1)2
The part in brackets is now equal to the left hand side of equation (**). So if we add to both sides of (**) the positive number 1/(n + 1)2, we get
( 1 + 1/4 + ... 1/n2 ) + 1/(n + 1)2 < ( 2 - 1/n ) + 1/(n + 1)2.

That's the part where we used the induction hypothesis (**). The rest of the proof is just a sequence of more rewritings and inequalities to show that 2 - 1/n + 1/(n + 1)2 in turn is smaller than 2 - 1/(n + 1), as we set out to prove. There are probably a lot of ways to do this, the one I prefer (which I gave in my post) is to write
1/n - 1/(n + 1)2 = 1/(n + 1) * (1 + x) < 1/(n + 1) * 1 = 1/(n + 1),
where x is some positive number.