Inequality of a recursive function

Question

Let $x_1=1$ and $x_{n+1}=\tfrac{1}{1+x_n}$. I want to proof that for every $n,m\in \mathbb{N}$ the inequality $|x_{n+1}-x_{m+1}|\leq \tfrac{1}{2}|x_n-x_m|$ is true. My idea is to somehow exchange $x_{n+1}-x_{m+1}$ with $\tfrac{1}{1+x_n}-\tfrac{1}{1+x_m}$. Maybe one can argue with Cauchy and the Epsilon-criteria?

Answer 1

We can easily prove by induction that for all $n$, $x_n \leqslant 1$.

So for all $n$, $x_{n+1} \geqslant 1/2$, which also means that for all $n\geqslant 2$, $x_n \geqslant 1/2$.

Then if we note $f:x\mapsto \frac{1}{1+x}$, we have $f'(x)=\frac{-1}{(1+x)^2}$, so $|f'(x)|=\frac{1}{(1+x)^2}$ which is decreasing with x (we consider $x\geqslant 0$). So for $x \geqslant 1/2$, we have $|f'(x)|\leqslant |f'(1/2)| = 4/9 \leqslant \frac{1}{2}$.

By the mean value theorem, we have that : $\forall (x,y) \in [1/2, +\infty[, |f(x)-f(y)|\leqslant \underset{z\geqslant 1/2}{\text{sup}} |f'(z)| |x-y|$

By replacing $x$ and $y$ by $u_n$ and $u_{n+1}$, we get the answer.

Answer 2

We can trivially get $$|x_{n + 1} - x_{m + 1}| = \frac{|x_m - x_n|}{(1 + x_n)(1 + x_m)},$$ so it is left to prove that $(1 + x_n)(1 + x_m) \geq 2$. You can notice that $$x_1 = 1, x_2 = \frac{1}{2}, x_3 = \frac{2}{3}, x_4 = \frac{3}{5}, x_5 = \frac{5}{8},\ ... $$ and in general $x_n = \frac{F_n}{F_{n+1}}$, where $F_n$ is the $n$-th term of the Fibonacci sequence. From $F_{n+1} = F_{n-1} + F_n$ and $F_n \geq F_{n-1} > 0$ we deduce that $x_n = \frac{F_n}{F_{n+1}} \geq \frac{1}{2}$. So $(1 + x_n)(1 + x_m) \geq (1 + \frac{1}{2})^2 > 2$, which is what we wanted.