I'm given:
$$\begin{align*} x_1&=\frac32\\\\ x_{n+1}&=\frac3{4-x_n} \end{align*}$$
How do I go about to formally prove the sequence converges and show it?
Thanks in advance.
$\endgroup$ 93 Answers
$\begingroup$We prove by induction that:
- $1<x_n<3$
- $x_n$ is decreasing.
The base case is obvious. Now assume that $1<x_{n-1}<3$ for some $n$. Then $$ \frac{3}{4-1}< \frac{3}{4-x_{n-1}}<\frac{3}{4-3} $$ or, after simplifying, $1<x_n<3$, so $1.$ holds for $n$. Also, note that $1<x_{n-1}<3$ implies $$ (x_{n-1}-1)(x_{n-1}-3)<0\Rightarrow 3<4x_{n-1}-x_{n-1}^2 $$ so $$ x_n=\frac{3}{4-x_{n-1}}<x_{n-1} $$ So $2.$ holds as well. Now by the monotone convergence theorem, $x_n$ converges. With a little more work, we can show that this limit is actually $1$.
$\endgroup$ 4 $\begingroup$Claim: $(x_{n})$ is monotonically decreasing.
The base case clearly holds.
Now assume true for $n=k+1$ for some $k \in \mathbb{Z_{+}}$.
So $x_{k+1}<x_{k}$
We can rearrange the terms in terms of its predecessors. Then we get
$$x_{k+1}=4-\frac{3}{x_{k+2}} \text{ , } x_{k}=4-\frac{3}{x_{k+1}} $$
Rearranging gives the desired result.
Claim: $x_{n}$ is bounded below.
Suppose not. Then for all $n^*$ larger than some $N \in \mathbb{Z_{+}}$,
$x_{n^*}<-4$ $\space$ (since $x_{n}$ is decreasing)
Now, this implies $4-x_{n^*}>8$ but then $x_{n^*+1}>1$ which is impossible.
$\endgroup$ $\begingroup$There is a theorem that says for any recursion $x_{n+1}=g(x_n)$, convergence is guaranteed whenever $| g'(x) |< 1$.
In our case, $g(x) = \frac{3}{4-x}$. This is clear since $x_{n+1} = g(x_n) = \frac{3}{4-x_n}$.
So lets evaluate the expression...
$g'(x) = \frac{3}{(4-x)^2}$, and we require $|g'(x)|<1$. Obviously $g'(x)$ is always positive.
We have $\frac{3}{(4-x)^2}<1$, which simplifies to $3 < (4-x)^2 = 16 - 8x + x^2$
If you solve the quadratic inequality you will see that $x>4+\sqrt{3}$ or $x<4-\sqrt{3}$.
The latter case, $x<4-\sqrt{3}\approx 2.26795\ldots$, is the case we are in. Since $x_1 = \frac32 = 1.5$, we are in the appropriate range for convergence.
If your initial term $x_1$ is not in the appropriate range, convergence can still happen. It's just not guaranteed and deeper analysis is required.
Also, just because $x_1$ isnt in the proper intervals doesnt necessarily mean that some other $x_i$ down the line wont be, and when/if that is the case, convergence is once again guaranteed. Once youre in the interval of convergence you stay there.
$\endgroup$
