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

Question

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

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 4

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.

Answer 5

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