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

Solution 1:

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:

Solution 2:

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.

Solution 3:

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