# Show that sequence approaches fixed point of a function

Problem Let $f(x)$ be a differentiable function on $\Bbb R$ with $\left|\,f ' (x)\right| \leq r < 1$, where $r$ is constant. Then consider the sequence $\{x_n\}$ such that $x_1 = 0$, $x_{n+1} = f(x_n)$, $n\geq1$. Show that $x_n \to x^*$ as $n$ approaches infinity. Moreover, $x^* = f(x^*)$.

Attempt I tried showing that when $f ' (x) = r$, then eventually you end up with $x_{n+1} = \sum_{n=1}^{\infty}r^n$. That sum converges by the $p$ test, so then $f(x)$ should converge to some number $x^*$. Then for $\epsilon>0$ there exists $N$ such that $n\geq N$ such that $$\left|\,f(x^*)-x^*\right| \leq \left|x_{n+1} - x_n\right| \leq \epsilon.$$ Then to show for $f ' (x) < r$ use direct comparison test to say the bigger series converges so the smaller one must converge as well.

I'm not sure if I can just do this or not, can someone let me know if I'm using the correct method or not?

• Hint: $\mathbb{R}$ is a complete metric space. If you can show that $\{x_n\}$ is Cauchy, then you get convergence immediately. To see that $\{x_n\}$ is Cauchy, you will want to show that for all $x,y \in\mathbb{R}$, $|f(x)-f(y)|\leq r|x-y|$. (This is a special case of a more general result called the Banach fixed point theorem.) – Gyu Eun Lee May 12 '13 at 22:54

The trick is to show the sequence is Cauchy, i.e. given any $\varepsilon >0$ there is some $N$ s.t.

$$|x_n-x_m|<\varepsilon$$

whenever $n,m>N$. The trick here is that you know that $\sum_i r^i$ converges, so you end up with an upper bound which is the tail $\sum_{i=N}^\infty r^i$. This converges to zero as $N\to \infty$. This should be enough hints to let you fill in the details.

• Since the sum of r^i converges, do I still need to do any sort of comparison test to show that the bigger sequence converges, or once I saw that this sequence is Cauchy, that's all I need to show? – Bashion May 12 '13 at 23:17
• You do know that the reals are complete, right? What does that imply about Cauchy sequences? – Edvard Fagerholm May 12 '13 at 23:23
• That implies Cauchy sequences converge right? So then since I'm showing that {xn} converges, and its in R, then sequence will always converge to some x* such that f(x*) = x*, right? – Bashion May 12 '13 at 23:29
• Yup. There is one more detail however. How do you know that $f(x^*)=x^*$? – Edvard Fagerholm May 13 '13 at 0:22