# Homework Help: Induction to get me through the night

1. Oct 18, 2007

### rock.freak667

1. The problem statement, all variables and given/known data
A sequence $${u_n}$$ is defined by $x_{n+1}=x_n^2 +\frac{1}{4} ,x_1<\frac{1}{2}$
Prove by mathematical induction or otherwise that:-
a)$x_{n+1}-\frac{1}{2}<0$
b)$x_{n+1}>x_n$
2. Relevant equations

3. The attempt at a solution
a)
Assume statement true for n=N

therefore
$$x_{N+1}-\frac{1}{2}<0$$

squaring both sides

$$x_{N+1}^2-x_{N+1} +\frac{1}{4}<0$$

$$x_{N+2}-x_{N+1}<0$$

$$x_{N+2}<x_{N+1}$$

$$-\frac{1}{2}$$

$$x_{N+2}-\frac{1}{2}<x_{N+1}-\frac{1}{2}$$

By the inductive hypothesis$x_{N+1}-\frac{1}{2}<0$

$$x_{N+2}-\frac{1}{2}<0$$

$$x_{N+2}<\frac{1}{2}$$

Therefore true for n=N+1. After testing $$x_1,x_2,x_3,...$$ true for all Natural numbers...
b) Assume true for n=N
$$x_{N+1}>x_N$$
sq.both sides
$$x_{N+1}^2>x_N^2$$

$$+\frac{1}{4}$$

$$x_{N+1}^2+\frac{1}{4}>x_N^2+\frac{1}{4}$$

$$x_{N+2}>x_{N+1}$$

hence true for n=N+1....etc etc..true for n an element of N

What would be the way to prove this in the "otherwise method"? (Not by exhaustion)

Last edited: Oct 18, 2007
2. Oct 18, 2007

### Kreizhn

I'm not terribly sure that your proof is correct, assuming that you're in a real space.

When you square both sides, you have a non-negativity condition, thus

$$x_{N+1}^2-x_N +\frac{1}{4}<0$$
is incorrect.

As a matter of fact, test the correctness of this statement using any $$x_1<\frac{1}{2}$$
This is corroborated by part(b). Since

$$x_{n+1}>x_n$$ then $$x_{N+1}^2-x_N +\frac{1}{4}>0$$

Furthermore, you squared both sides in part (b) and went from

$$x_{N+1}^2>x_N$$
to
$$x_{N+1}^2>x_N^2$$

Last edited: Oct 18, 2007
3. Oct 18, 2007

### rock.freak667

Ahhh...typos i shall fix now...but explain to me that non-negativity thing

4. Oct 18, 2007

### Kreizhn

Well, any time you square something real, you get something non-negative, with it equaling zero iff it's precisely equal to zero.

Edit: Use $$x_{n+2} = x_{n+1}^2 +\frac{1}{4}$$ then to get

$$x_{n+2} - x_{n+1} > 0$$

$$x_{n+1}^2 - x_{n+1} + \frac{1}{4} > 0$$

However in your proof you have

$$x_{n+1}^2 - x_{n+1} + \frac{1}{4} < 0$$

A contradiction if you ignore the non-negativity of a square, but believe part (b) is correct.

Don't you hate inequalities :P

Last edited: Oct 18, 2007
5. Oct 18, 2007

### Kreizhn

Instead, assume that $$x_n - \frac{1}{2} < 0$$

Then clearly $$x_n < \frac{1}{2}$$

Now consider $$x_{n+1}$$ and make the substitution
$$x_{n+1} = x_n^2+\frac{1}{4}$$

Then apply the induction hypothesis.

6. Oct 18, 2007

### rock.freak667

If I sub $$x_n+1$$ I would get
$$x_{N}^2-x_N +\frac{1}{4}>0$$ Which is true as a perfect square is always >0 , isnt the end result to get it in the form $$x_{N+1}>x_N$$

7. Oct 18, 2007

### Kreizhn

I've changed my reply above so that it looks more like the line in your proof. You see, in your proof you've stated that

$$x_{N+1}^2-x_{N+1} +\frac{1}{4}<0$$

but this cannot be true both because of the non-negativity of squares and because of part (b) directly.

Edit: If you're talking about part (b), you want to show that if we've assumed $$x_{n} > x_{n-1}$$ then it follows that

$$x_{n+1} > x_n$$.

To show this, it is sufficient to show that $$x_{n+1} - x_n > 0$$

Now substitute $$x_{n+1} = x_n^2+\frac{1}{4}$$

into that equation above and apply part (a). Then you'll have your result.

Last edited: Oct 18, 2007
8. Oct 18, 2007

### rock.freak667

I still think this inequality thing is messing me up

9. Oct 18, 2007

### Kreizhn

Now you've squared both sides. So $$x_{N+1}^2-x_{N+1} +\frac{1}{4}$$ cannot be less than zero, even though it was before you squared it.

Consider $$-4 < 0$$. Square both sides, is it still true that
$$16 < 0$$

10. Oct 18, 2007

### rock.freak667

Well seems induction is kinda messing me up here; but i solved part b) using otherwise method by considering $$x_{n+1}-x_n$$ and that is the perfect square which is always greater than zero so then$$x_{n+1}-x_n>0$$ and it is proven but part a) is a bit tricky

EDIT:Typo in part a) it is supposed to be $$x_n<\frac{1}{2}$$ not n+1

Last edited: Oct 18, 2007
11. Oct 18, 2007

### Kreizhn

We want to show that, assuming $$x_n - \frac{1}{2} < 0$$ then $$x_{n+1}-\frac{1}{2} < 0$$

It is sufficient to show that $$x_{n+1} < \frac{1}{2}$$. Thus consider $$x_{n+1}$$

Now we know that $$x_{n+1} = x_n^2+\frac{1}{4}$$ and so we can substitute this to get

$$x_{n+1} = x_n^2+\frac{1}{4}$$. Now we apply the induction hypothesis that $$x_n < \frac{1}{2}$$

and the result follows

12. Oct 18, 2007

### rock.freak667

so then it's basically like
$$x_{n+1}=(<\frac{1}{2})^2+\frac{1}{4}$$
and so x_{n+1} will be <1/4 and hence <1/2 ?

13. Oct 18, 2007

### Kreizhn

you might want to try that addition again.

$$x_{n+1} = x_n^2 + \frac{1}{4}$$
$$x_{n+1} < \left( \frac{1}{2} \right)^2 + 1/4$$
$$x_{n+1} < \frac{1}{4} + \frac{1}{4}$$
$$x_{n+1} < \ldots$$

14. Oct 18, 2007

### rock.freak667

Well it's basically the same thing..although my teacher suggested to not right up proofs like that

15. Oct 18, 2007

### Dick

This is so simple if you avoid the induction stuff. Which you seem to be allowed to do. The sequence is defined by iterating the function f(x)=x^2+1/4. a) says to prove that if x<1/2 then f(x)<1/2. b) says to prove if x<1/2 then f(x)>x. The first is really simple and the second is easily solved by figuring out where f(x)-x is positive. In case you are interested in another approach.

16. Oct 18, 2007

### Kreizhn

Well, no offense to anyone, but it's simple with the induction stuff as well, though it can be a little daunting if you don't do it a lot. However, myself being an algebraist will almost always find doing the algebra easier than the analysis.

Furthemore, I claim finding out where $$f^n(x) - f^{n-1}(x) > 0$$ is not as simple as you seem to make it out to be. We're analyzing a recursively defined function, so it's not as simple as you say, unless you can show me a proof that in applying it to the first iteration it holds for all iterations (which I'm not sure you can do without induction).

Edit: If your method worked in general, you would be able to show that $$x_{n+1} = \sqrt{2 + \sqrt{x_n}}$$ where $$x_1 =1$$ has a finite limit by showing that there is a maximum for the function $$f(x) = \sqrt{2+\sqrt{x}}$$ over the real domain, which is clearly not true.

Last edited: Oct 18, 2007
17. Oct 18, 2007

### Dick

No offense taken. Everybody has their favorite methods. But if you show if 0<x<1/2 implies f(x)<1/2, and f(x)-x>0, I think you have the whole thing. Without induction. But, sorry to interrupt.

18. Oct 18, 2007

### Kreizhn

I'm sorry, but I'm really not following the logic of your argument. The inductive analog to what you've said here is that if it holds for the base case, it must hold for all n, which in general is not correct. Can you justify your reasoning?

19. Oct 18, 2007

### Dick

I've said if x is in (0,1/2) then f(x) is in (0,1/2). So if x0 is in (0,1/2), f(x0) is in (0,1/2) . Since f(x0) is in (0,1/2), f(f(x0)) is in (0,1/2). Since f(f(x0)) is in (0,1/2) then f(f(f(x0))) is in (0,1/2). I suppose that is induction.

20. Oct 18, 2007

### Kreizhn

Yeah, it is induction. And so to prove it in general we'd have to use an inductive step, which really doesn't make it any easier.