Prove that the sequence $x_{n+1}=\frac{a}{1+x_n}$ with $a,x_0>0$ converges

Prove that the sequence $x_{n+1}=\frac{a}{1+x_n}$ with $a,x_0>0$ converges

Im having a lot of trouble with this exercise... indeed I think that the statement is false. The unique tools that I have to solve this exercise is the algebra of limits, the $\epsilon{-}N$ definition of convergence of a sequence and the theorem that says that if a sequence is monotone and bounded then converges.

If $(x_n)\to x$ then $x=\frac{-1+\sqrt{1+4a}}2$. From some tests and watching the graph of the function $\frac{1}{1+x}$ the sequence certainly is alternating.

Then I tried to prove that the sequence $(x_{n+2}-x_n)$ is monotone but I failed. Some hint or solution, with the tools already mentioned, will be appreciated. Thank you.

Hint: Let $\xi_a=\frac{-1+\sqrt{1+4a}}{2}$ and $f_a(x)=\frac{a}{1+x}$.

1. Prove that if $x_n<\xi_a$, then $f_a(x_n)=x_{n+1}>\xi_a$ and vice-versa;
2. Prove that $f_a(f_a(x))=a\left(1-\frac{a}{1+x+a}\right)$ is an increasing function on $\mathbb{R}^+$, and deduce that both the sequences $\{x_{2n}\}_{n\geq 0}$ and $\{x_{2n+1}\}_{n\geq 0}$ are monotonic and bounded, hence converging;
3. Prove that $\lim_{n\to +\infty}x_{2n}=\lim_{n\to +\infty}x_{2n+1}$, for instance by bounding $|x_{n}-x_{n+1}|$, or by noticing that $|f_a'(\xi_a)|=\frac{4a}{(1+\sqrt{1+4a})^2}<1$ and by invoking the Banach fixed point theorem;
4. Once you get $\lim_{n\to +\infty}x_n = L$, prove that, by the continuity of $f_a$, $L$ has to fulfill $L=f_a(L)$, from which $L=\xi_a$.

The following picture might be inspiring:

• With $x_{n+2}=a\cdot\frac{1+x_{n-1}}{1+x_{n-1}+a}$ is easy to see that if $0<a<1$ the subsequence decreases and is bounded below by zero. But the case $a\ge 1$ is not easy. – Masacroso Oct 20 '16 at 19:49
• @Masacroso: $f_a(f_a(x)) = a\cdot\frac{x+1}{1+x+a}$ is always monotonic if $a>0$, it does not matter if $a<1$ or $a>1$. – Jack D'Aurizio Oct 20 '16 at 20:10
• Aaahh... I see. I can check that $$x>a\cdot\frac{1+x}{1+x+a}\implies x^2>0$$ what is always true. – Masacroso Oct 20 '16 at 20:17
• One last question Jack, what software you used to draw this picture? – Masacroso Oct 20 '16 at 20:18
• @Masacroso: GeoGebra – Jack D'Aurizio Oct 20 '16 at 20:19

Let $f(x)=\frac{a}{1+x}$

we have

$\forall n\geq0 \; x_{n+1}=f(x_n)$

it is easy to see ( by induction) that

$\forall n\geq0 \; \; x_n>0$.

the only fixed point of $f$ in this interval is $L=\frac{-1+\sqrt{1+4a}}{2}$.

assume now that $0<x_0<L$.

$f$ is decreasing at $(0,+\infty)$, thus

by induction, we can prove that

1. $(x_{2n})$is increasing.
2. $(x_{2n+1})$ is decreasing.
3. $0<x_{2n}<L$
4. $L<x_{2n+1}<a$

the two sequences are then convergent.

let $L_1=\lim_{n\to \infty}x_{2n+1}$

and

$L_2=\lim_{n\to\infty}x_{2n}$

we have

$L_1=\frac{a}{1+L_2}$ and $L_2=\frac{a}{1+L_1}$

which gives $L_1=L_2=L$.

the second case is similar.

This probably isn't the intended solution, but it can be solved with some linear algebra:

Consider the linear recurrence $X_{n+1} = AX_n$, where $$X_0 = \begin{pmatrix}x_0\\1\end{pmatrix}, \quad A = \begin{pmatrix}0 & a\\1 & 1\end{pmatrix}.$$ Then you can show that $x_n = X_{n,1} / X_{n,2}$. The eigenvalues of $A$ are $\lambda_1 = \frac{1 + \sqrt{1+4a}}{2}$ and $\lambda_2 = \frac{1 - \sqrt{1+4a}}{2}$, and by diagonalizing $A$ you can compute explicitly $X_n = A^n X_0$ and show that $$x_n = \frac{a \lambda_1^n (\lambda_2 x_0 - a) + a \lambda_2^n (-\lambda_1 x_0 + a)}{\lambda_1^{n+1} (\lambda_2 x_0 - a) + \lambda_2^{n+1} (-\lambda_1 x_0 + a)} \to \frac{a}{\lambda_1} = -\lambda_2$$ since $\lambda_2 x_0 - a \ne 0$ (because $\lambda_2 < 0)$ and $|\lambda_1| > |\lambda_2|$.

This idea generalizes to the case where $x_{n+1}$ is any rational function of $x_n$, by letting $X_n$ be a vector of powers of $x_n$.