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?

  • $\begingroup$ 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.) $\endgroup$ – 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.


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.

  • $\begingroup$ 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? $\endgroup$ – Bashion May 12 '13 at 23:17
  • $\begingroup$ You do know that the reals are complete, right? What does that imply about Cauchy sequences? $\endgroup$ – Edvard Fagerholm May 12 '13 at 23:23
  • $\begingroup$ 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? $\endgroup$ – Bashion May 12 '13 at 23:29
  • $\begingroup$ Yup. There is one more detail however. How do you know that $f(x^*)=x^*$? $\endgroup$ – Edvard Fagerholm May 13 '13 at 0:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.