# The limit of a simple sequence recursively defined

Given a real number $a>0$, $(x_n)$ is recursively defined by $$\begin{cases} x_1=a\\ x_{n+1}=\frac{2x_n+1}{x_n+2} \end{cases}$$ Find a proof that $(x_n)$ is convergent and then find the limit.

Can anyone give me a hint on how to determine the limit of a sequence like that? I tried to write the first terms to see if I could find an equation that was not recursive for the $n$-th term, but I failed miserably. I dont really know how to find the answer to that without such equation.

Grateful for any help!

• Once you determined that the sequence converges (and only after that), assume that the limit is $L\,$, then pass the recurrence relation to the limit and solve $L = (2L+1) / L+2\,$.
– dxiv
Jul 28 '17 at 3:07
• On the contrary, first you should solve $L = (2L + 1)/(L + 2)$ to find what the limit should be, then you should proceed to prove that this $L$ really is a limit Jul 28 '17 at 3:09
• @BoltonBailey The point of my comment was that you can not find the limit of a sequence this way unless you first prove that the sequence does in fact converge. Take for example $x_{n+1}=-x_n\,$, using your approach the limit would come up as $0\,$, which of course it's not.
– dxiv
Jul 28 '17 at 3:13

HINT: if the sequence converges in $\Bbb R$ then applying limits both sides of the definition of $x_{n+1}$ we get

$$\lim_{n\to\infty} x_{n+1}=\lim_{n\to\infty} \frac{2 x_n+1}{x_n+2}\implies L=\frac{2L+1}{L+2}\implies L^2=1\implies L=1$$

where we had discarded $L=-1$ because the sequence $(x_n)$ is positive so it cannot converges to $-1$.

Then suppose that the limit of the sequence is $1$ and divide by cases. If $0<a<1$ then $x_1<x_2<1$, so you can try to setup a proof by induction to show that $x_n<1$ for all $n\in\Bbb N$ and that the sequence $(x_n)$ is strictly increasing.

If $a>1$ then $x_1>x_2$ and you can try to setup a proof by induction to show that the sequence $(x_n)$ is strictly decreasing and positive.

If the above fails for some case then you can try to show that the sequence doesnt converges to $1$, and because $1$ is the unique possible candidate for the limit then the sequence doesnt converge for the studied case.

An alternative method is studying the fixed points of $f(x):=\frac{2x+1}{x+2}$ in $(0,\infty)$. In this case we can see that $f$ is a contraction in this region (because $|f'(x)|<1$ for $x\in(0,\infty)$), so it converges to a unique fixed point in this region.

Since $a_1>0$ the the recursive def'n of $a_{n+1}$ implies,by induction on $n,$ that $a_n>0$ for all $n.$

Let $a_n=1+d_n.$ We have $a_n>0$ so $d_n>-1.$ By direct calculation we have $$d_{n+1}=a_{n+1}-1=[(2a_n+1)/(a_n+2)]-1=d_n/(3+d_n).$$

Now $d_n>-1\implies 3+d_n>2,$ so $$|d_{n+1}|=|d_n|/|3+d_n|\leq |d_n|/2.$$

The result $|d_{n+1}|\leq |d_n|/2$ implies that $d_n\to 0$ and hence $a_n\to 1.$

Note: The first sentence of the Answer by Masacroso shows you how to deduce that if $L=\lim_{n\to \infty}$ exists, then $L^2=1.$ And since $a_n>0$ for all $n,$ if $L$ exists then $L=1.$

Coincidence! I just added a similar answer to another question using matrices.

Note: This is to answer your question about a non-recursive formula for the $n^{th}$ term (and consequently to find the limit). Also note that this is a very general approach for solving such problems.

$$x_n = \frac{p_n}{q_n}$$

where

$$p_{n+1} = 2p_n + q_n$$ $$q_{n+1} = p_n + 2q_n$$

[You can consider $s_n = p_n + q_n$ and do something clever, but we won't go there as we want a general approach]

Thus

$$A^n \begin{bmatrix}a\\1\end{bmatrix} = \begin{bmatrix}p_n\\q_n\end{bmatrix}$$

Where

$$A = \begin{bmatrix}2&1\\1&2\end{bmatrix}$$

This matrix is diagonalizable and gives the general form of $p_n$ and $q_n$ to be

$$u3^n + v (-1)^n$$

($3$ and $-1$ are the eigenvalues of $A$)

I will leave it to you to compute the the formulae for $p_n$ and $q_n$, which will prove convergence of $x_n$.

btw, the limit is $1$, because the matrix $A$ is symmetric. $A^n$ will be symmetric with entries of the form $x3^n + y(-1)^n$, and so the $u$ for $p_n$ will be the same as the $u$ for $q_n$ and the limit is their ratio.

When you have a sequence $x_{n+1}=f(x_n)$ with f(x) an increasing function ($f'(x)>0$).

You can prove the fact that the sequence has a ceiling (or a floor) and is increasing (or decreasing) by induction :

using the property of increasing function f : $a < b \Rightarrow f(a) < f(b)$

example :

if $x_{n} < L \Rightarrow f(x_{n})=x_{n+1} < f(L)=L$ the sequence has a ceiling. Provided that $x_1<L$

if $x_{n} < x_{n+1} \Rightarrow f(x_{n})=x_{n+1} < f(x_{n+1})=x_{n+2}$ the sequence is going up. Provided that $x_1<x_2$

Then you use the theorem : an increasing sequence with a ceiling necessarily converges. (or the other way)