Using induction to prove convergence

[sassie]

Homework Statement

Let a sequence (x(n)) by x1 = 0 and x(n+1) =[1 + 2x(n) − x^2(n)]/3

Show it converges.

Homework Equations

The Attempt at a Solution

Prove bounded above and is increasing. i.e. x(n)<x(n+1)<1

base case: 0<1/3<1

k+1 case: not very sure - i know that i will need to use the squeeze theorem, but I'm stuck on how the k+1 case expression will look like and what to use squeeze on.

i get x(k+2) being [14-8x(k)-4x^2(k)-4x^3(k)+x^4(k)]/27

do i need to use this to show x(k+1)<x(k+2)<1 ? then what do i use squeeze on? how do I show this is the case? I'm really stuck, any hints would be greatly appreciated! :)

 

[JG89]

To show the sequence is bounded above by 1, notice that $$-(x_n - 1)^2 < 1$$, since the left hand side of the inequality is a negative value. Add two to both sides and divide both sides by 3 and you get $$\frac{2 - (x_n-1)^2}{3} < 1$$. Now expand the quadratic in the numerator and simplify.

And though it may not be the best way, if you can show that for each n $$x_n \ge 0$$ then showing it is increasing is easy.

 

[fmam3]

Here's my attempt. As first suggested by JG89, first show that $$\frac{2 - (x_n - 1)^2}{3} < 1$$ holds. This will show that $$x_n$$ is bounded above by 1 for all $$n \in \mathbb{N}$$.

Next, we need to show that $$x_n \geq 0$$ for all $$n \in \mathbb{N}$$. For contradiction, suppose there exists some $$N+1 \in \mathbb{N}$$ such that $$x_{N+1} < 0$$. So we have that $$0 < \frac{1 + 2x_N - x_N^2}{3}$$, implying that $$0 < 2 - (x_N - 1)^2$$. Do some further rearranging, get $$2 > (x_N - 1)^2 \geq 0$$ and finally, get $$\sqrt{2} + 1 > x_N \geq 1$$ --- contradiction to the prior where we had shown that $$x_n < 1$$ for all $$n \in \mathbb{N}$$.

Next, we show that the sequence $$(x_n)$$ is monotonically increasing. To show that $$x_{n+1} \geq x_n$$ for all $$n$$ is equivalent to showing $$x_{n+1} - x_n \geq 0$$. So, consider that $$x_{n+1} - x_n = \frac{1 + 2x_n - x_n^2}{3} - x_n = \frac{1 + 2x_n - x_n^2 - 3x_n}{3} = \frac{1 - x_n - x_n^2}{3} \geq \frac{1 - x_n}{3} > 0$$ and the last inequality holds because we had previously shown that $$0 \leq x_n < 1$$ holds.

Hence, by the monotone convergence theorem, the sequence $$(x_n)$$ converges.

In fact, we can do better than that --- we will find the limit. Note that if $$\lim x_n = x$$, then $$\lim x_{n+1} = x$$ (this is easy to prove). Hence, from the original recurrence relation, we can have $$x^2 = \frac{1 + 2x - x^2}{3}$$. Using the typical quadratic formula, we solve to get $$x = \frac{-1 \pm \sqrt{5}}{2}$$ and we reject the negative root since we had shown that $$x_n \geq 0$$, which implies $$\lim x_n \geq 0$$. Hence, $$\lim x_n = (-1 + \sqrt{5})/2$$.

 

[fmam3]

Just a further note --- I don't think this problem is quite appropriate for the Squeeze Theorem. The Squeeze Theorem states that if $$\lim a_n = \lim b_n = L$$ and we have that $$a_n \leq s_n \leq b_n$$ for all $$n \in \mathbb{N}$$, then $$\lim s_n = L$$. Notice here that we already known before hand that the limit (i.e. L) for the purpose of squeezing already exists. In this problem, you want to show the convergence, which implies you do not know that the limit exists (yet).