# Show that $\lim x_n$ exists.

Consider the sequence $x_n$ defined by $x_{n+1}=\dfrac{x_n+3}{3x_n+1}$ with $0<x_1<1$.

Show that $\lim x_n$ exists.

My try:

Let $x_1=a$ then $x_2=\dfrac{a+3}{3a+1},x_3=\dfrac{5a+3}{3a+5},x_4=\dfrac{7a+9}{9a+7},x_5=\dfrac{17a+15}{15a+17}$.

If I assume the limit to exist then it can be found out to be $1$,but how to show that the limit exists actually?

• Take $x_{2n}$ and $x_{2n+1}$ separately because one is decreasing, the other is increasing. – user261263 Dec 16 '17 at 5:53

If $$x_{n+1}=\frac{x_n+3}{3x_n+1}$$ then $$\frac{x_{n+1}-1}{x_{n+1}+1}=-\frac12\frac{x_n-1}{x_n+1}$$ Therefore, $$\bbox[5px,border:2px solid #C0A000]{x_n=\frac{1+\left(-\frac12\right)^n\frac{x_0-1}{x_0+1}}{1-\left(-\frac12\right)^n\frac{x_0-1}{x_0+1}}}$$

• I thought the problem was to show that $x_n$ converges. – robjohn Dec 16 '17 at 7:46
• Wonderful solution ! – MrMaths Dec 16 '17 at 8:18

Let $f : x \in \mathbb{R}_{+}\mapsto \dfrac{x + 3}{3x+1}$.

$f$ is a homographic function, and since $1 \times 1 - 3 \times 3 < 0$, $f$ is decreasing.

$f(0) = 3$ and $f(3) = \dfrac{3}{5}$ therefore $f([0,3]) \subset [0,3]$.

As $x_1 \in [0,3]$, it gives :

$\forall n \in \mathbb{N}^{*}, 0 \leq x_n \leq 3$.

Moreover,

$\forall n \in \mathbb{N}^{*}, x_{n+1} - x_n = 3\dfrac{x_n^2 + 1}{3x_n+1} > 0$.

$(x_n)$ is therefore increasing and has an upper bound : it converges, and lim $x_n$ exists.

• How do you know $f$ is decreasing – Learnmore Dec 16 '17 at 12:53
• Look at its derived function... 😉 – MrMaths Dec 16 '17 at 12:58
• Just note the terms let $x_1=0.4,x_2=1.54,x_3=0.808...$ – Learnmore Dec 16 '17 at 13:03
• Do you still feel the same that it's decreasing – Learnmore Dec 16 '17 at 13:03
• $f$ is decreasing but $(x_n)$ is not. – MrMaths Dec 16 '17 at 15:27


Set $\ds{x_{n} \equiv {p_{n} \over q_{n}}}$ such that $\ds{x_{n + 1} = {x_{n} + 3 \over 3x_{n} + 1}}$ becomes $\ds{{p_{n + 1} \over q_{n + 1}} = {p_{n} + 3q_{n} \over 3p_{n} + q_{n}}}$. Then, choose $\ds{p_{n + 1} = p_{n} + 3q_{n}\quad\mbox{and}\quad q_{n + 1} = 3p_{n} + q_{n}}$ such that the original sequence is identically satisfied.

The above setting is equivalent to ( $\ds{\sigma_{i}}$ with $\ds{i = x,y,z}$ is a Pauli Matrix ) \begin{align} {p_{n + 1} \choose q_{n + 1}} & = \pars{\begin{array}{cc} \ds{1} & \ds{3} \\ \ds{3} & \ds{1} \end{array}} {p_{n} \choose q_{n}} = \pars{1 + 3\sigma_{x}}{p_{n} \choose q_{n}} \end{align}

For simplicity, scalars as added quantities to matrices are implicitly multiplied by the identity matrix.

Then, \begin{align} {p_{n + 1} \choose q_{n + 1}} & = \pars{1 + 3\sigma_{x}}^{\, 2}{p_{n - 1} \choose q_{n - 1}} = \pars{1 + 3\sigma_{x}}^{\, 3}{p_{n - 2} \choose q_{n - 2}} = \cdots = \pars{1 + 3\sigma_{x}}^{\, n}{p_{1} \choose q_{1}} \end{align}

Note that $\ds{\pars{\totald[2]{}{k} - 1}\exp\pars{k\sigma_{x}} = 0\,;\qquad \left.\exp\pars{k\sigma_{x}}\right\vert_{\ k\ =\ 0} = 1\,,\quad \left.\totald{\exp\pars{k\sigma_{x}}}{k}\right\vert_{\ k\ =\ 0} = \sigma_{x}}$

because $\ds{\sigma_{x}^{2} = 1}$ $\ds{\implies \exp\pars{k\sigma_{x}} = \cosh\pars{k} + \sinh\pars{k}\sigma_{x}}$ such that \begin{align} \pars{1 + 3\sigma_{x}}^{n} & = n!\bracks{z^{n}}\exp\pars{z\bracks{1 + 3\sigma_{x}}} = n!\bracks{z^{n}}\exp\pars{z}\exp\pars{3z\sigma_{x}} \\[5mm] & = {1 \over 2}\,n!\bracks{z^{n}}\bracks{\pars{\expo{4z} + \expo{-2z}} + \pars{\expo{4z} - \expo{-2z}}\sigma_{x}} \\[5mm] & = {1 \over 2}\braces{\bracks{4^{n} + \pars{-2}^{n}} + \bracks{4^{n} - \pars{-2}^{n}}\sigma_{x}} \\[5mm] & = 2^{n - 1}\pars{\begin{array}{cc} \ds{2^{n} + \pars{-1}^{n}} & \ds{2^{n} - \pars{-1}^{n}} \\ \ds{2^{n} - \pars{-1}^{n}} & \ds{2^{n} + \pars{-1}^{n}} \end{array}} \end{align} and \begin{align} x_{n + 1} & = {p_{n + 1} \over q_{n + 1}} = {\bracks{2^{n} + \pars{-1}^{n}}p_{1} + \bracks{2^{n} - \pars{-1}^{n}}q_{1} \over \bracks{2^{n} - \pars{-1}^{n}}p_{1} + \bracks{3^{n} + \pars{-1}^{n}}q_{1}} \\[5mm] \implies & \bbx{x_{n + 1} = {\bracks{2^{n} + \pars{-1}^{n}}x_{1} + 2^{n} - \pars{-1}^{n} \over \bracks{2^{n} - \pars{-1}^{n}}x_{1} + 2^{n} + \pars{-1}^{n}}} \end{align}