Evaluate limit of sequence without using Banach fixed-point theorem

Let sequence $\{x_n\}$ is defined following: $$x_1=2,\quad x_2=2+\dfrac{1}{2},\quad x_3=2+\dfrac{1}{2 + \dfrac{1}{2}}, \cdots$$

Evaluate $\lim \limits_{n\to \infty}x_n$.

My sketch proof: I thought that $\{x_{2n-1}\}$ increases but $\{x_{2n}\}$ decreases. For any $n$ we have $2\leqslant x_n<3$. In that case both subsequences converges to same limit hence $\{x_n\}$ also converges to that limit.

The main question is how to prove that $\{x_{2n-1}\}$ increases and $\{x_{2n}\}$ decreases. Can anyone help to me please?

P.S. Please do not diplicate this topic with this because here was using Banach fixed-point theorem.

• Well, you have to use recursion and induction a lot. I tried to do that, but it took me a lot of ink and paper. After the original question has been closed, I gave up. – Crostul Oct 28 '15 at 14:35
• @Crostul, sorry please but you mean to use induction? – ZFR Oct 28 '15 at 14:38
• Look at the wiki page on continued fractions, esp the theorems 1-5 on the properties satisfied by the convergents. – Aravind Oct 28 '15 at 14:39

Hint: If $x_n<x_{n+2}$ then $$x_{n+1}=2+\frac1{x_n}>2+\frac1{x_{n+2}}=x_{n+3}$$ and in the same way $x_{n+2}<x_{n+4}$.

In the same way, one finds for index difference $1$ if $x_n<x_{n+1}$ then $x_{n+1}>x_{n+2}$.

In short, it is easy to prove your assertions with induction, using $x_1<x_2$ and $x_1<x_3$ as induction start to show

• $\{x_{2m-1}\}_{m\in\Bbb N}$ increasing,
• $\{x_{2m}\}_{m\in\Bbb N}$ decreasing and
• $x_{2k-1}<x_{2n-1}<x_{2n}<x_{2m}$ for all $k,m$ and some $n\ge\max(k,m)$
• Dear LutzL! Are you using here math induction? – ZFR Oct 28 '15 at 16:06
• Yes, using $x_1<x_2$ and $x_1<x_3$ to show $x_{2m-1}$ increasing, $x_{2m}$ decreasing and $x_{2k-1}<x_{2n-1}<x_{2n}<x_{2m}$ for some $n\ge\max(k,m)$. – LutzL Oct 28 '15 at 16:24
• Really nice solution! Thanks a lot, dear LutzL! :) – ZFR Oct 28 '15 at 16:32

Hint: Write $x_n = \tfrac{a_n}{b_n}$. Then we have a sequence $(a_n,b_n)$ of natural numbers satisfying $$\pmatrix{a_{n+1}\\b_{n+1}} = \pmatrix{2&1\\1&0}\pmatrix{a_n\\b_n}.$$ With just a bit of linear algebra, this allows you to find an explicit form for $x_n$ as a fraction. If you can do this, then you'll be easily able to conclude.

• For this we must find $n$th power of $2\times 2$ matrix right? – ZFR Oct 28 '15 at 14:50
• @RFZ Exactly.${}$ – Daniel Robert-Nicoud Oct 28 '15 at 18:17

We have $x_{n+1}=2+1/x_n.$ Assuming the limit $L$ exists ,we have $L\geq 2$ and $L=2+1/L.$This is valid because if we put $$a_n=L+d_n$$ then $$L+d_{n+1}=2+1/(L+d_n)$$ which cannot hold for non-zero $L$ and for values $d_{n+1},d_n$ arbitrarily close to $0$ unless $L=2+1/L$....Now $$L>0\wedge L=2+1/L\iff L>0\wedge L^2=2L+1\iff L=1+\sqrt 2.$$ To see that $a_n$ actually does converge to $1+\sqrt 2$, put $$a_n=1+\sqrt 2+d_n=L+d_n.$$ $$\text {Then } L+d_{n+1}=2+1/(L+d_n)$$ which (using the simplifying formula $L^2=2L+1$ ) implies $$|d_{n+1}|= |d_n(2-L)/(2+d_n)|=|d_n(2-L)/a_n|\leq |d_n(2-L)/2|=|d_n|(\sqrt 2-1)/2.$$ Since $0<(\sqrt 2-1)/2<1$,we have $\lim_{n\to \infty}d_n=0$.Observe how exploring the consequences of an assertion can help to prove or disprove it: "Assuming the limit exists...."