7
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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}$$

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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}$$

$\endgroup$
1
$\begingroup$

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} $$

$\endgroup$
  • $\begingroup$ Thank you very much for your answer, just wondering what does representing on the projective line mean? $\endgroup$ – Monolite Dec 25 '15 at 17:16
  • $\begingroup$ 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 $\endgroup$ – David Holden Dec 25 '15 at 17:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.