# Thread: Contraction mapping theorem

1. ## Contraction mapping theorem

0<c<1 and |f(x)-f(y)<c|c-y|
a) Show f is continuous on all of R
b)Pick some point y1 in R and construct the sequence (y1,f(y1),f(f(y1)),....)
In general if y_(n+1)=f(yn) show that the resulting sequence yn is a Cauchy sequence. hence we may let y=limyn
c)Prove that y is a fixed point of f and that is unique in this regard.
d) Finally prove that if x is any arbitrary point in R then the sequence (x,f(x),f(f(x)),...) converges to y defined in (b).

a) want to show if |x-c|<delta then |f(x)-f(c)|<epsilon
b) A sequence is Cauchy if |an-am|<epsilon
c)want to show f(y)=y

2. Originally Posted by kathrynmath
0<c<1 and |f(x)-f(y)<c|c-y|
a) Show f is continuous on all of R
It's much, much stronger than continuous. If you're allowed to use the limit definition of continuity just note that $\displaystyle \displaystyle 0\leqslant \lim_{x\to y}|f(x)-f(y)|\leqslant \lim_{x\to y}c|x-y|=0$
b)Pick some point y1 in R and construct the sequence (y1,f(y1),f(f(y1)),....)
In general if y_(n+1)=f(yn) show that the resulting sequence yn is a Cauchy sequence. hence we may let y=limyn
Note that by induction $\displaystyle d\left(f^{m+1}(y_1),f^{m}(y_1)\right)<c^m d\left(f(y_1),y_1\right)$. Thus, we see that

\displaystyle \begin{aligned}d\left(f^{n+k}(y_1),f^n(y_1)\right) &\leqslant \sum_{j=0}^{k-1}d\left(f^{n+j+1}(y_1),f^{n+j}(y_1)\right)\\ &< \sum_{j=0}^{k-1}c^{n+j}d\left(f(y_1),y_1\right)\\ &< \frac{c^n}{1-c}d\left(f(y_1),y_1\right)\end{aligned}

From where it evidently follows, letting $\displaystyle n\to\infty$ that $\displaystyle \left\{f^{n}(y_1)\right\}_{n\in\mathbb{N}}$ is Cauchy, and thus by the completeness of $\displaystyle \mathbb{R}$ it follows that $\displaystyle y=\lim f^{n}(y_1)$ exists.
c)Prove that y is a fixed point of f and that is unique in this regard.
Uniqueness is clear in general since if $\displaystyle x\ne y$ but $\displaystyle f(x)=x,f(y)=y$ then we see our conditions state that $\displaystyle d(x,y)=d\left(f(x),f(y)\right)<cd(x,y)<d(x,y)$

Now, to see that $\displaystyle y$ is a fixed point we merely note that since $\displaystyle \lim f^n(y_1)=y$ that $\displaystyle \lim f^{n+1}(y_1)=y$ and so by the continuity of $\displaystyle f$ we have that $\displaystyle f(y)=f\left( \lim f^n(y_1)\right)=\lim f^{n+1}(y_1)=y$

d) Finally prove that if x is any arbitrary point in R then the sequence (x,f(x),f(f(x)),...) converges to y defined in (b).
Merely note that $\displaystyle y_1$ was arbitrary to begin with.

Remark: There is a much more elegant way of proving that a contractive map from a complete metric space to itself has a fixed point.

3. What are all the d's? If they are derivatives, we haven't gotten to derivatives yet.

4. Originally Posted by kathrynmath
What are all the d's? If they are derivatives, we haven't gotten to derivatives yet.
Distance function...absolute value.

5. ok what about the lim f^n and lim f^(n+1). I guess I'm not seeing what f^n is

6. Originally Posted by kathrynmath
ok what about the lim f^n and lim f^(n+1). I guess I'm not seeing what f^n is
Look here.

7. I'm not sure how d follows from y1 being arbitrary in b. I do notice we have similar sequences.