Finding the limit of $x_1=0 , x_{n+1}=\frac{1}{1+x_n}$

I have had big problems finding the limit of the sequence $x_1=0 , x_{n+1}=\frac{1}{1+x_n}$. So far I've only succeeded in proving that for $n\geq2$: $x_n>0\Rightarrow x_{n+1}>0$

(Hopefully that much is correct: It is true for $n=2$, and for $x_{n+1}>0$ exactly when $\frac{1}{1+x_n}>0$, which leads to the inequality $x_n>-1$ which is true by the induction assumption that $x_n>0$.)

On everything else I failed to come up with answers that make sense (such as proving that $x_{n+1}>x_n \forall n\geq1$). I'm new to recursive sequences, so it all seems like a world behind the mirror right now. I'd appreciate any help, thanks!

Solution 1:

It is obvious that $f:x\mapsto\frac1{1+x}$ is a monotonically decreasing continuous function $\mathbf R_{\geq0}\to\mathbf R_{\geq0}$, and it is easily computed that $\alpha=\frac{-1+\sqrt5}2\approx0.618$ is its only fixed point (solution of $f(x)=x$). So $f^2:x\mapsto f(f(x))$ is a monotonically increasing function that maps the interval $[0,\alpha)$ into itself. Since $x_3=f^2(x_1)=\frac12>0=x_1$ one now sees by induction that $(x_1,x_3,x_5,...)$ is an increasing sequence bounded by $\alpha$. It then has a limit, which must be a fixed point of $f^2$ (the function mapping each term of the sequence to the next term). One checks that on $ \mathbf R_{\geq0}$ the function $f^2$ has no other fixed point than the one of $f$, which is $\alpha$, so that must be value of the limit. The sequence $(x_2,x_4,x_6,...)$ is obtained by applying $f$ to $(x_1,x_3,x_5,...)$, so by continuity of $f$ it is also convergent, with limit $f(\alpha)=\alpha$. Then $\lim_{n\to\infty}x_n=\alpha$.

Solution 2:

Here is a way to show that the sequence converges to the unique positive solution to $a=1/(1+a)$: Define $f(x)=1/(1+x)$. Then $f'(x)=-1/(1+x)^2$. For every $n$, the mean value theorem gives $$x_{n+1}-a=f(x_n)-f(a)=(x_n-a)f'(c_n)$$ for some $c_n$ between $x_n$ and $a$. Since $-1<f'(x)<0$ for all $x>0$, this shows that $\lvert x_n-a\rvert$ decreases with $n$. Moreover, we already have $f'(1/2)=-4/9$, and $f'$ is increasing, so $-4/9<f'(c_n)<0$ for all $n\ge2$. Thus $\lvert x_n-a\rvert$ decreases at least as fast as $(4/9)^n$, i.e., geometrically. In particular, the $x_n-a\to0$.

Addendum: To do this without differentiation, just rely on the computation $$f(x)-f(y)=\frac1{1+x}-\frac1{1+y}=\frac{y-x}{(1+x)(1+y)}$$ instead.

Solution 3:

Firstly, I'd like to thank everybody who contributed! Your insight helped me greatly in understanding the problem. Here is my solution (one that I feel is more down to earth in terms of mathematical skills used!)

It is easy enough to prove that $x_n\in[0,1] \forall n$ through induction. Now we definitely have a bounded sequence.

However, it is not monotonic and after some investigation, one can see that it seems to oscilate around its limit $\frac{\sqrt{5}-1}{2}$ - that is, if it actually converges!

Now the crucial step. I used the expression $x_{n+2}=\cfrac{1}{1+\cfrac{1}{1+x_n}}$ to check for which values it is monotonic, which lead to this:

$x_{n+2}>x_n$ for $x_n\in(0,\frac{\sqrt{5}-1}{2})$

$x_{n+2}<x_n$ for $x_n>\frac{\sqrt{5}-1}{2}$

Thus we have two subsequences, both of which are bounded and monotonic and converging to the same limit, only from two different sides.

This answer isn't probably full, but the additional proofs needed are trivial enough, this was the most important step I needed to take to get to the answer.

Solution 4:

Let $\omega\gt0$ such that $\omega^2+\omega=1$, then $x_{n+1}-\omega=-\omega\cdot\frac1{1+x_n}\cdot(x_n-\omega)$ hence $$ |x_n-\omega|\leqslant\omega^n\cdot|x_0-\omega|, $$ and the rest is easy since $\omega\lt1$.

Solution 5:

If you're willing to assume the sequence converges to a number $x$, then you can see that $x = \frac{1}{1 + x}$, and then you can solve for $x$.