Sequence defined by $x_{n+1}=\frac{1}{1+x_n}.$

Question

Problem:

A sequence is defined by $$\left\{ \begin{array}{rcr} x_1 & = & 1 \\ x_{n+1} & = & \frac{1}{1+x_n} \\ \end{array} \right., \quad \quad n=1,2,....$$

Examine if the sequence is convergent/divergent. If the former, compute the limit.

---

Questions:

This is an exam question that was given on an exam in my university a few years ago. It gave 6 points.

1. I can't find a way to make condition 3 to be met. I get that $k=1$, but for the criteria to hold it has to be that $k<1.$ Why doesn't this work?
2. Would I get full points with this method, If I found a way to solve question 1? Earlier I did a similar problem with this method but instead I had the sequence defined by

$$\left\{ \begin{array}{rcr} x_1 & = & \sqrt{3} \\ x_{n+1} & = & \sqrt{3+x_n} \\ \end{array} \right., \quad \quad n=1,2,....$$

and this method worked.

---

Solution:

This recurrence relation is an iteration of the form $x_{n}=f(x_{n-1})$. Lets take some help from the help-equation $$f(x)=\frac{1}{1+x}, \quad x>0.$$ According to Banach Fixed Point Theorem, If $x_n$ converges, it converges to the unique solution of the equation $x=f(x).$ In order to apply Banach Fixed Point Theorem, three criteria has to be met:

1. $f$ has to be defined and continous in an interval $[a,b]$
2. $x\in[a,b] \Longrightarrow f(x)\in[a,b]$
3. $f$ is differentiable in $[a,b]$ and there should exist a constant $k$ such that $$|f'(x)|\leq k<1.$$

Choosing $I=[0,2]$ I have that:

1. In this interval, there are no problems for the continuity nor the definition of the function. OK!
2. We have that $1\leq f(x) \leq1/2 \Longrightarrow f(x)\in[0,2] \ \forall \ x\in[0,2].$ OK!
3. $f$ is also differentiable in this interval and we have that $$|f'(x)|=\left|-\frac{1}{(1+x)^2}\right|\leq 1 \leq1,$$

Here is where the trouble starts. However, using the Banach's Theorem, I still get correct answer.

$$x=f(x)=\frac{1}{1+x} \Longleftrightarrow x^2+x-1=0 \Longleftrightarrow x_{1,2}=\frac{\pm\sqrt{5} - 1}{2},$$

but since $x>0,$ it follows that $$\lim_{n\rightarrow \infty}x_n=\frac{\sqrt{5}-1}{2}.$$

Why does this work despite not meeting the criteria number 3?

Answer 1

I think you just chose too wide interval. Try $[\frac12, 1]$ which gets mapped into $[\frac12,\frac23]\subseteq [\frac12,1] $. Also, if $f (x)=\frac {1}{1+x} $, then $|f'(x)|=\frac {1}{(1+x)^2}\le \frac49\lt 1$ so you can have $k=\frac49$.