# Prove that a given recursion sequence converges

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?

• Is $(x_n)_{n\in \Bbb N}$ decreasing? Is $(x_n)_{n\in \Bbb N}$ bounded below? Nov 6, 2013 at 14:37
• What I wrote is all I am given. Nov 6, 2013 at 14:45
• Let me rephrase: prove that $(x_n)_{n\in \Bbb N}$ is both decreasing and bounded below. Do you know how proving this helps you? Nov 6, 2013 at 14:46
• If it's bounded below, I can assume the sequence converges right ? And showing it's decreasing will let me find the limit ? Nov 6, 2013 at 14:54
• No, for instance $(\sin(n))_{n\in \Bbb N}$is bounded below and it doesn't converge. You need something more to be sure it converges. Nov 6, 2013 at 14:56

We prove by induction that:

1. $1<x_n<3$
2. $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$.

• Isn't it enough to show that it's bounded below by one and decreasing in order to prove the limit is 1 ? Nov 8, 2013 at 14:32
• @GinKin No. It's also bounded below by $0$ or $1/2$; you have to prove that $1$ is the infimum. Nov 9, 2013 at 16:00
• Maybe not completely rigorous, but since the sequence converges, for sufficiently large $n$ we get $a_{n+1}=a_{n}$. Thus if the desired limit is $L$, solving $L=\frac{3}{4-L}$ yields $L=1$. Nov 10, 2013 at 5:00
• Thanks you two. I went throught all of my notes and searched online and still can't really figure out how to prove 1 is the infimum for this question in a rigorus way. Nov 10, 2013 at 15:35

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}

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.

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.