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
<br /> x_{N+1}-\frac{1}{2}&lt;0

squaring both sides

x_{N+1}^2-x_{N+1} +\frac{1}{4}&lt;0

x_{N+2}-x_{N+1}&lt;0

x_{N+2}&lt;x_{N+1}

-\frac{1}{2}

x_{N+2}-\frac{1}{2}&lt;x_{N+1}-\frac{1}{2}

By the inductive hypothesisx_{N+1}-\frac{1}{2}&lt;0

<br /> x_{N+2}-\frac{1}{2}&lt;0

x_{N+2}&lt;\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}&gt;x_N
sq.both sides
x_{N+1}^2&gt;x_N^2

+\frac{1}{4}

x_{N+1}^2+\frac{1}{4}&gt;x_N^2+\frac{1}{4}

x_{N+2}&gt;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}&lt;0
is incorrect.

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

x_{n+1}&gt;x_n then x_{N+1}^2-x_N +\frac{1}{4}&gt;0


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

x_{N+1}^2&gt;x_N
to
x_{N+1}^2&gt;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} &gt; 0

x_{n+1}^2 - x_{n+1} + \frac{1}{4} &gt; 0

However in your proof you have

x_{n+1}^2 - x_{n+1} + \frac{1}{4} &lt; 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} &lt; 0

Then clearly x_n &lt; \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}&gt;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}&gt;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}&lt;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} &gt; x_{n-1} then it follows that

x_{n+1} &gt; x_n.

To show this, it is sufficient to show that x_{n+1} - x_n &gt; 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

<br /> x_{N+1}-\frac{1}{2}&lt;0

squaring both sides

x_{N+1}^2-x_{N+1} +\frac{1}{4}&lt;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 &lt; 0. Square both sides, is it still true that
16 &lt; 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 thenx_{n+1}-x_n&gt;0 and it is proven but part a) is a bit trickyEDIT:Typo in part a) it is supposed to be x_n&lt;\frac{1}{2} not n+1

 

[Kreizhn]

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

It is sufficient to show that x_{n+1} &lt; \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 &lt; \frac{1}{2}

and the result follows

 

[rock.freak667]

so then it's basically like
x_{n+1}=(&lt;\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} &lt; \left( \frac{1}{2} \right)^2 + 1/4
x_{n+1} &lt; \frac{1}{4} + \frac{1}{4}
x_{n+1} &lt; \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) &gt; 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.