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:

enter image description here

  • $\begingroup$ 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. $\endgroup$ – Masacroso Oct 20 '16 at 19:49
  • $\begingroup$ @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$. $\endgroup$ – Jack D'Aurizio Oct 20 '16 at 20:10
  • 1
    $\begingroup$ Aaahh... I see. I can check that $$x>a\cdot\frac{1+x}{1+x+a}\implies x^2>0$$ what is always true. $\endgroup$ – Masacroso Oct 20 '16 at 20:17
  • 1
    $\begingroup$ One last question Jack, what software you used to draw this picture? $\endgroup$ – Masacroso Oct 20 '16 at 20:18
  • 2
    $\begingroup$ @Masacroso: GeoGebra $\endgroup$ – 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}$



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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.