This question already has an answer here:

Let $f : [a,b] \rightarrow [a,b]$ be a continuous function s.t. $f'(x)$ is defined on $(a,b)$ and $\left\lvert f'(x)\right\rvert \leqq t$ where $0<t<1$. Prove that for any point $x_0$ in $[a,b]$ the sequence defined by $$ x_n=f(x_{n-1}), n>0$$ converges to one unique fixed point.

Attempt: Frankly, I have struggled to make a real attempt due to the fact that I can't find notes relating to this.

Obviously, I am assuming that there exists $x$ in$ [a,b]$ s.t. $f(x)=x$ but how do I relate the sequence to this $x$?

I'm strictly not allowed to assume Banach's theorem in this question, nor the Cauchy sequence because they come up on the second part of the course. I rather have to PROVE this.


marked as duplicate by rtybase, Eevee Trainer, mrtaurho, Vinyl_cape_jawa, José Carlos Santos Mar 7 at 13:30

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Another related question. $\endgroup$ – rtybase Mar 6 at 22:36

The Mean Value Theorem tells you that the sequence $\{x_n \}$ is Cauchy because $|f(y)-f(x)| \leq t|y-x|$, so for $m \lt n, |x_m-x_n| \leq |x_1-x_2|\sum_{k=m}^nt^k \leq 2M \frac{t^m}{1-t}$ (where $M = \max \{f(x)~|~x \in [a, b]\}$. The space $[0, 1]$ is complete, so since the sequence is Cauchy (choose $m$ sufficiently large that $\frac{2Mt^m}{1-t} \lt \epsilon$), it must converge.

  • $\begingroup$ MVT does not immediately tell you that $(x_n)$ is Cauchy. You have to provide more details. $\endgroup$ – Kavi Rama Murthy May 10 at 23:10
  • $\begingroup$ @KaviRamaMurthy Edited to add details. $\endgroup$ – Robert Shore May 11 at 0:20

To prove this from scratch note that by MVT $$|x_n-x_m| \leq |x_{m+1}-x_m|+|x_{m+2}-x_{m+1}|$$ $$+\cdots+|x_{n}-x_{n-1}|\leq |x_{m+1}-x_m| (1+t+t^{2}+\cdots+t^{n+m-1})$$ for $n >m$. Also $|x_{m+1}-x_m| \leq t^{m-1} |x_2-x_1|$. Using the convergence of the geometric series $\sum t^{n}$ conclude that $\{x_n\}$ is Cauchy. If $x =\lim x_n$ then the definition of $x_n$'s and continuity of $f$ tells you that $f(x)=x$. Uniqueness follows easily by MVT.

  • $\begingroup$ Thank you! This is very helpful :-) $\endgroup$ – Gracious Mar 7 at 9:20

This can be proved using the Banach Fixed Point Theorem.

Intuitively, the BFPT tells us that if there is some function $F$ such that the distance between any two points $x$ and $y$ (when scaled by a constant $q$) is always larger than the distance between the corresponding images ($F(x)$ and $F(y)$), then the sequence $$x_n = F(x_{n-1}) $$ will converge to a unique fixed point. For a more rigorous treatment of the BFPT statement: https://en.wikipedia.org/wiki/Banach_fixed-point_theorem.

Since in this case you know that $$|f'(x)| \leq t $$ This implies that

$$\Big|\frac{f(x) - f(y)}{x - y}\Big| \leq t$$

for all possible points $x,y \in [a,b]$. Think about why this is the case (Hint: Use the mean value theorem).

This implies that

$$| f(x) - f(y)| < t |x-y| $$

which is what the BFPT requires. From here, we can just apply the BFPT to state that there is a fixed point in $[a,b]$ for the sequence

$$ x_n = f(x_{n-1})$$

  • $\begingroup$ Should probably expressly mention that the space $[0, 1]$ is complete, since that is a necessary condition for the Banach fixed point theorem to hold. For an easy counterexample demonstrating that you need completeness, consider $f(x) = x/2$ on $(0, 1]$. $\endgroup$ – Robert Shore Mar 6 at 22:50
  • $\begingroup$ @RobertShore Yes, you are right, thanks! $\endgroup$ – Sean Lee Mar 6 at 22:52

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