# On a recursive sequence exercise.

I have the following recursive sequence of which I want to prove the convergence:

$$x_{n+1} = \frac{x_n +1}{x_n +2 }$$ and $x_1 = 0$

I have proved that it is bounded above by $1$ and that it is increasing by taking the derivative, but I am told to do it without using derivatives.

How could I show that it's bounded and increasing using only elementary methods?

In particular I would like to prove that it is bounded by $\frac{\sqrt{5} - 1}{2}$ (this is the limit), but any additional ways to solve it are obviously very appreciated.

BOUNDED: $$x_{n+1}=\frac{x_n+1}{x_n+2}=1-\frac{1}{x_n+2}<1 \, \forall \, n \in \mathbb{N}$$ Hence $\{x_n\}$ is bounded above by $1$.

MONOTONIC NATURE:

Say $P(n):x_{n+1}>x_n \, \forall \, n \in \mathbb{N}$ be the induction statement.

For $n=1$, $x_2=\frac{1}{2}>0=x_1$

So $P(1)$ is true.

Assume $P(n)$ is true for some $k$, $k \in \mathbb{N}$.

So we get $$x_{k+1}>x_k$$ or $$x_{k+1}+2>x_{k}+2$$ or $$\frac{1}{x_{k+1}+2}<\frac{1}{x_{k}+2}$$ or $$-\frac{1}{x_{k+1}+2}>-\frac{1}{x_{k}+2}$$ or $$1-\frac{1}{x_{k+1}+2}>1-\frac{1}{x_{k}+2}$$ or $$\frac{x_{k+1}+1}{x_{k+1}+2}>\frac{x_{k}+1}{x_{k}+2}$$ or $$x_{k+2}>x_{k+1}$$

Hence $P(n)$ is true by mathematical induction.

LIMIT: Say $\lim_{n\to\infty} x_n = l$

$$l=\frac{l+1}{l+2}$$ or $$l^2+2l=l+1$$ or $$l^2+l-1 \Rightarrow l= \frac{1+\sqrt{5}}{2}$$

Often, when a sequence $x_n$ has a limit $a$, it's interesting to study $u_n=x_n-a$ instead. Here we will take $u_n=a-x_n$, but it's the same idea. Of course, we don't know in advance that $a$ is the limit, it's just a guess.

Let $a=\frac{\sqrt{5}-1}{2}$, and $u_n=a-x_n$. Notice that $a^2=1-a$, and that $x_n\geq0$.

We would like to prove that $u_n$ is positive and decreasing, and tends to $0$.

$$u_{n+1}=a-x_{n+1}=a-\frac{a-u_n+1}{a-u_n+2}$$ $$u_{n+1}=\frac{a^2-au_n+2a-a+u_n-1}{x_n+2}=\frac{u_n(1-a)+a^2+a-1}{x_n+2}$$ $$u_{n+1}=u_n\frac{(1-a)}{x_n+2}$$

And since $0<\dfrac{1-a}{x_n+2}\leq\dfrac{1-a}{2}<1$, you have that if $u_n>0$, then $u_{n+1}>0$ as well, thus $u_n>0$ for all $n$ (since $u_1=a>0$).

Also, $u_{n+1}<u_n\dfrac{1-a}{2}<u_n$, and the sequence $u_n$ is decreasing (thus $x_n$ is increasing).

Finally,

$$0<u_n<u_1\left(\frac{1-a}{2}\right)^{n-1}\underset{n\to\infty}{\longrightarrow}0$$

Hence $u_n\to0$ and $x_n\to a$.

A note about the initial "guess" $a=\frac{\sqrt{5}-1}{2}$. When you are given a sequence $u_{n+1}=f(u_n)$ with a continuous function $f$, then if $u_n$ has a limit, it must be a solution of the equation $L=f(L)$. Thus you can find the possible candidates for a limit. Here the equation is

$$L=\frac{1+L}{2+L}$$ $$L^2+L-1=0$$

And you find that it has solutions $\dfrac{-1\pm\sqrt{5}}{2}$, one of which is negative, thus not a good candidate since $x_n\geq0$. The other is our $a$.

If $x_n$ has a limit, it's thus $a$. The purpose of the first part of the answer is to prove that $x_n$ is indeed convergent. Actually, once you know $u_n$ is positive and decreasing, you know it's convergent (see here), thus also $x_n$. I added a more direct proof since it's easy here, and it gives you also the rate of convergence.

Functions of the form $f:\; x \mapsto \dfrac{ax+b}{cx+d}$ are fractional linear transformations, and their iterates can be computed in closed form: $f^n: x \mapsto \dfrac{a_n x + b_n}{c_n x + d_n}$ where the matrix $\pmatrix{a_n & b_n\cr c_n & d_n} = \pmatrix{a & b\cr c & d\cr}^n$. In your case $$\pmatrix{a & b\cr c & d\cr} = \pmatrix{1 & 1\cr 1 & 2\cr}$$ and it's not hard to show that $$\pmatrix{a_n & b_n\cr c_n & d_n\cr} = \pmatrix{F_{2n-1} & F_{2n}\cr F_{2n} & F_{2n+1}}$$ where $F_n$ are the Fibonacci numbers. In particular, with $\phi = \dfrac{1+\sqrt{5}}{2}$ is the "golden ratio", we have $F_n \sim \phi^n$ as $n \to \infty$. With $x_1 = 1$ we get $$x_n = f^{n-1}(1) = \dfrac{F_{2n-3} + F_{2n-2}}{F_{2n-2} + F_{2n-1}} = \dfrac{F_{2n-1}}{F_{2n}} \to 1/\phi = \dfrac{-1+\sqrt{5}}{2}$$

represent your sequence as points $(x_n,1)$ on the projective line.

then $$(x_{n+1},1) = (x_{n},1)\begin{bmatrix} 1 & 1 \\ 1 & 2 \end{bmatrix}$$ let $\bar v$ be any element of the projective line. then it is easy to show $$\bar v\begin{bmatrix} 1 & 1 \\ 1 & 2 \end{bmatrix}^n = \bar v\begin{bmatrix} f_n & f_{n+1} \\ f_{n+1} & f_{n+2} \end{bmatrix} = \bar v\begin{bmatrix} \frac{f_n}{f_{n+1}} & 1 \\ 1 & \frac{f_{n+2}}{f_{n+1}} \end{bmatrix} \to \bar v\begin{bmatrix} \theta^{-1} & 1 \\ 1 & \theta \end{bmatrix}$$ where $\theta$ is the golden ratio. substituting $(1,1)$ for the first term the limit is seen to be: $$\frac{\theta^{-1}+1}{1+\theta} = \frac1{\theta}$$

• Thank you very much for your answer, just wondering what does representing on the projective line mean? – Monolite Dec 25 '15 at 17:16
• the property of the projective line useful here is that for any nonzero $t$ the point $(x,y)$ is the same as the point $(tx,ty)$. this saves us worrying that the matrix gets larger and larger with each power. this is why the main sequence of equations is expressed as operations on a point, and what permits the second equality. expressing things like this was only a device to keep the arithmetic as simple as possible. i'm sorry if it created an obstacle – David Holden Dec 25 '15 at 17:27