# solution of recurrence relation $x_{n+1} = \frac {1}{x_n + 1}$

$$x_{n+1} = \frac {1}{x_n + 1}; x_1 > 0$$

How to transform it into the form $x_n =$? I need the solution in order to check if it converges at any $x_1 > 0$.

-
You do know that you don't necessarily need the solution in order to check for convergence, right? – user1337 Jul 3 '13 at 18:33
No matter what you put in there for $x_n$, it's pretty obvious that $x_{n+1}$ is less than $1$. At least once it's been pointed out. As for convergence, a limit $x$ needs to statisfy $$x = \frac{1}{x + 1}$$ since it can't be a limit unless it's a stationary point. Now just solve that equation and check that for any $x_n$, $x_{n+1}$ is closer to this $x$. – Arthur Jul 3 '13 at 18:35
And that means $x_{n+2}$ is larger than ... – Daniel Fischer Jul 3 '13 at 18:35
Check the convergence of monotone sequences. – Mhenni Benghorbal Jul 3 '13 at 18:37
@MhenniBenghorbal This sequence isn't monotone. If you consider every other term, however, then it is. – Arthur Jul 3 '13 at 18:38

hint

One nice way to do linear fractional recurrences is to use matrices. If $a/b=x$, then $c/d = 1/(x+1)$, where \left(\begin{aligned}0\qquad 1 \cr 1\qquad 1\end{aligned} \right) \left(\begin{aligned}a\cr b\end{aligned}\right) = \left(\begin{aligned}c\cr d\end{aligned}\right) So we can get a formula for $x_n$ if we know a formula for the $n$th power of that $2 \times 2$ matrix.

-

Some hints:

1. First of all you can prove by induction that all of the $x_n$'s are strictly positive.
2. Using that, prove that they are also lesser than 1.
3. From the above two steps, the sequence $\{ x_n \}$ lies in the compact interval $[0,1]$,so it has a convergent subsequence $\{ x_{n_k} \}$
4. Prove that $\lim_{n \to \infty} x_n$ exists and is equal to $\lim_{k \to \infty} x_{n_k}$.
-

Try

$$a(n)\to \frac{\mathcal C \;\left(\frac{1}{2} \left(1+\sqrt{5}\right)\right)^n+\left(\frac{1}{2} \left(1-\sqrt{5}\right)\right)^n}{\mathcal C \; \left(\frac{1}{2} \left(1+\sqrt{5}\right)\right)^{n+1} +\left(\frac{1}{2} \left(1-\sqrt{5}\right)\right)^{n+1}}$$

-
These look like Fibonacci numbers to me! – Ali Jul 3 '13 at 19:07

Let $a=\lim_{n\to\infty}x_n$. Then

\begin{align} &a=\frac{1}{1+\frac{1}{1+\frac{1}{1+...}}}\\&a=\frac{1}{1+a}\\&a(a+1)=1\\&a^2+a-1=0\\&a=\frac{-1\pm\sqrt{5}}{2} \end{align}

Since there is no negative term or subtraction in the sequence, we omit the negative solution.

$\displaystyle \therefore a=\lim_{n\to\infty}x_n=\frac{\sqrt{5}-1}{2}$

-

If you are interested in finding the limit, assume $\lim_{n\to \infty} a_n = a$, then

$$a=\frac{1}{a+1} \implies a^2+a-1=0 \implies a=\frac{-1 \bar{+} \sqrt{5}} {2}.$$

Now, you should pick up the right limit.

-