# Prove that the sequence $x_{n+1} = {\frac{x_n+1}{x_n+2}}, x_0 = 1$ converges to $\frac{1}{\varphi}$

I've established that $(x_n)$ is monotonically decreasing, but don't know if I should attempt to show that $\frac{1}{\varphi}$ is the infimum of $(x_n)$ or use another method.

-
@RagibZaman Sorry, edited. – bipartite_ Oct 7 '12 at 13:55

You know it is monotonically decreasing and clearly it is bounded by 0, so it must tend to some limit $L.$ So since $x_n \to L$, taking limits of the recursion gives $$L = \frac{L+1}{L+2}.$$ Can you use this to find $L$?

Probably not what was intended for your analysis class but neat anyway: Let $x_n = \dfrac{y_{n+1}}{y_n} - 2$ with $y_0=y_1=1$ so your recursion becomes $y_{n+1}-3y_{n+1}+y_n=0.$ We can explicitly solve for the general term of $y_n$ and thus $x_n$ but we don't need that here. All we need is that $y_n = A \lambda_1^n + B \lambda_2^n$ for $\lambda_1 = \varphi+1$ and $|\lambda_2|<1$ so $x_n \to \varphi+1 -2= \dfrac{1}{\varphi}.$

-
Gosh, that was stupid of me. Well, thanks for your help! – bipartite_ Oct 7 '12 at 13:59
@maxerize I've added an alternative method in my edit. If you find my answer acceptable, then please consider accepting my answer :) . – Ragib Zaman Oct 7 '12 at 14:18

Consider $a$ is the positive root of the equation $x^2 + x - 1 = 0$ We have $a^2 + a - 1 = 0, \ \dfrac{1-2a}{1-a} = - a$.

firstly, we proof $x_n > a, \forall n \ge 1$ by induct:

for n = 1, $x_1 = 1 > a$ is right.

If $x_n > a,$ then $x_{n+1} -a = \dfrac{x_n + 1}{x_n + 2} - a = \dfrac{(1-a)x_n + 1 - 2a}{x_n + 2}$

$x_{n+1} - a = (1-a) \dfrac{x_n + \dfrac{1-2a}{1-a}}{x_n + 2} = (1-a) \dfrac{x_n - a}{x_n + 2} > 0$

Implying $x_{n+1} > a$

Now we proof sequence ${x_n}$ decreasing:

Consider $x_{n+1} - x_n = \dfrac{x_n + 1}{x_n + 2} - x_n = \dfrac{1 - x_n - x_n^2}{x_n + 2}$

$x_{n+1} - x_n = \dfrac{a + a^2 - x_n - x_n^2}{x_n + 2} = \dfrac{(a - x_n)(1 + a + x_n)}{x_n + 2} < 0$

Sequance ${x_n}$ decreasing, bounded below so that it tends to $a$ which is the positive root of the equation $a = \dfrac{a + 1}{a+2}$.

$a = \dfrac{-1 + \sqrt{5}}{2} = \dfrac{1}{\varphi}$

-