# 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? – Git Gud Nov 6 '13 at 14:37
• What I wrote is all I am given. – GinKin Nov 6 '13 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? – Git Gud Nov 6 '13 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 ? – GinKin Nov 6 '13 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. – Git Gud Nov 6 '13 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 ? – GinKin Nov 8 '13 at 14:32
• @GinKin No. It's also bounded below by $0$ or $1/2$; you have to prove that $1$ is the infimum. – egreg Nov 9 '13 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$. – tc1729 Nov 10 '13 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. – GinKin Nov 10 '13 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.