Induction to get me through the night

[rock.freak667]

Homework Statement

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$

Homework Equations

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)

 

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

 

[rock.freak667]

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

 

[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

 

[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.

 

[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 , isn't the end result to get it in the form $$x_{N+1}>x_N$$

 

[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.

 

[rock.freak667]

I still think this inequality thing is messing me up

 

[Kreizhn]

Homework Statement

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

squaring both sides

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

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

 

[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 trickyEDIT:Typo in part a) it is supposed to be $$x_n<\frac{1}{2}$$ not n+1

 

[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

 

[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 ?

 

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

 

[rock.freak667]

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

 

[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.

 

[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.

 

[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.

 

[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?

 

[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.

 

[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.

 

[Dick]

If the range of a function defined on (0,1/2) is in (0,1/2), then the iterates of the function are in (0,1/2). If f(x)>x on (0,1/2) then the iterates are also increasing. There is an 'inductive' looking component when you map it to sequence language. But I don't have to prove anything else. It's done.