2
$\begingroup$

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!

  • 0
    http://math.stackexchange.com/questions/38739/convergence-of-a-n1-frac11a-n2013-04-20

5 Answers 5

5

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

  • 0
    Thanks! Your answer in particular got me to the final idea I used to prove this, only I used the sort of math I know how to use :)2012-11-13
3

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

  • 1
    Thanks. I do understand your approach, although at this point I'd never come up with it myself. Still, isn't there a more 'elementar' way of proving this? Or rather - there has to be one!2012-11-12
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} 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.

  • 0
    Like that approach. +12012-12-30
2

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

1

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

  • 0
    @did: Oh, that one is quite well known … but that is a very different story. However, thanks for the link to the *Monthly* article about it. It was new to me.2012-11-12