# Prove the Contraction Mapping Theorem.

Prove the Contraction Mapping Theorem.

Let $(X,d)$ be a complete metric space and $g : X \rightarrow X$ be a map such that $\forall x,y \in X, d(g(x), g(y)) \le \lambda d(x,y)$ for some $0<\lambda < 1$. Then $g$ has a unique fixed point $x^* \in X$, and it attracts everything, i.e. for any $x_0 \in X$ , the sequence of iterates $x_0, g(x_0), g(g(x_0))$, ... converges to the fixed point $x^* \in X$.

The hint I am given are for existence and convergence - prove that the sequence is Cauchy. For uniqueness, choose two fixed points of $g$ and apply the map to both.

Still a bit do not know how to proceed after looking at the hint. Could anyone help me based on those hints?

• Hint: $d(x_{n+1},x_n)=d(g(x_n),x_n)=d(g(g(x_{n-1})),g(x_{n-1}))\le \lambda d(g(x_{n-1}),x_{n-1})=d(x_n,x_{n-1})$ – J.R. Feb 8 '14 at 19:17
• @TooOldForMath: what are you trying to achieve here? – afsdf dfsaf Feb 8 '14 at 19:19
• I am giving you a hint so you can solve it. This is how it goes. Repeating what I wrote gives you $d(x_{n+1},x_n)\le \lambda^n d(x_1,x_0)$. Now $\lambda$ is between $0$ and $1$, so what happens when $n\rightarrow\infty$...? – J.R. Feb 8 '14 at 19:26
• why $\lambda d(g(x_{n-1}), x_{n-1}) = d(x_n, x_{n-1})$? – afsdf dfsaf Feb 8 '14 at 19:52
• $d(x_{n+1},x_n)\le \lambda d(x_n,x_{n-1}) \le \lambda^2 d(x_{n-1},x_{n-2})\le\cdots\le \lambda^n d(x_1,x_0)$ – J.R. Feb 9 '14 at 0:13

From

$$d(x_{n+1},x_n)=d(g(g(x_{n-1})),g(x_{n-1}))\le \lambda d(g(x_{n-1}), x_{n-1})=d(x_n,x_{n-1})$$

we get after $n$ applications of that inequality

$$d(x_{n+1},x_n)\le \lambda d(x_n,x_{n-1}) \le \lambda^2 d(x_{n-1},x_{n-2}) \le \cdots\le \lambda^n d(x_1,x_0)\tag{1}$$

Now we want to show that $(x_n)_n$ is a Cauchy sequence. So let $\epsilon>0$.

We assume $x_1\not=x_0$ (otherwise $x_0$ is already a fixed point). Set $c=d(x_1,x_0)>0$.

Since $0<\lambda<1$, the sum $\sum_{n=0}^\infty \lambda^n$ converges (to $1/(1-\lambda)$). Therefore we can pick $N$ large enough such that

$$\sum_{k=n}^\infty \lambda^k<\frac{\epsilon}{c}$$

for all $n\ge N$.

Then for $m>n\ge N$ we have by the triangle inequality

$$d(x_m,x_n)\le \sum_{k=n}^{m-1} d(x_{k},x_{k+1})$$

Applying $(1)$ we obtain

$$d(x_m,x_n)\le c\sum_{k=n}^{m-1} \lambda^k\le c\sum_{k=n}^\infty \lambda^k<c\cdot\frac{\epsilon}{c}=\epsilon$$

So $(x_n)_n$ really is a Cauchy sequence. Since $(X,d)$ is complete, it converges to a limit $x\in X$.

By the equation $x_{n+1}=g(x_n)$, the limit satisfies $x=g(x)$, so it is a fixed point.

Uniqueness is trivial, let $y$ be another fixed point of $g$. Then

$$d(x,y)=d(g(x),g(y))\le \lambda d(x,y)$$

If now $x\not=y$, then $d(x,y)>0$, so we can divide by $d(x,y)$ to obtain $\lambda\ge 1$, a contradiction. Therefore, $x=y$.

• "Therefore we can pick $N$ large enough such that $$\sum_{k=n}^\infty \lambda^k<\frac{\epsilon}{c}$$ for all $n\ge N$." For this part, do you backfill $$\frac{\epsilon}{c}$$ after going through the following: "Then for $m>n\ge N$ we have by the triangle inequality $$d(x_m,x_n)\le \sum_{k=n}^{m-1} d(x_{k},x_{k+1})$$ Applying $(1)$ we obtain $$d(x_m,x_n)\le c\sum_{k=n}^{m-1} \lambda^k\le c\sum_{k=n}^\infty \lambda^k<c\cdot\frac{\epsilon}{c}=\epsilon$$"? – afsdf dfsaf Feb 9 '14 at 17:18
• Backfill? What are you talking about? This is a logically complete argument. – J.R. Feb 9 '14 at 17:25
• I just mean whether we get to go through the following part: "Then for $m>n\ge N$ we have by the triangle inequality $$d(x_m,x_n)\le \sum_{k=n}^{m-1} d(x_{k},x_{k+1})$$ Applying $(1)$ we obtain $$d(x_m,x_n)\le c\sum_{k=n}^{m-1} \lambda^k\le c\sum_{k=n}^\infty \lambda^k<c\cdot\frac{\epsilon}{c}=\epsilon$$" before filling $$\frac{\epsilon}{c}$$ in the "Therefore we can pick $N$ large enough such that $$\sum_{k=n}^\infty \lambda^k<\frac{\epsilon}{c}$$ If not, how did you get $$\sum_{k=n}^\infty \lambda^k<\frac{\epsilon}{c}$$? – afsdf dfsaf Feb 9 '14 at 17:36
• Please stop copying all this stuff in the comments. It makes it really unreadable. You are not "filling" $\epsilon/c$ whatever you mean by that. The logic is like this: $c$ is a constant defined as $d(x_1,x_0)$. It is fixed. Now I throw you an $\epsilon>0$ in the beginning. And now you notice, aha, the sum $\sum_{k=1}^\infty \lambda^k$ converges therefore sequence of truncated sums $\sum_{k=n}^\infty \lambda^k$ converges to $0$ for $n\rightarrow\infty$. So it will eventually be smaller than that given $\epsilon/c$. Let us say that the point when it becomes smaller is reached at $N$ – J.R. Feb 9 '14 at 17:42
• $\sum_{k=n}^\infty \lambda^k <\epsilon/c$ for all $n$ bigger than $N$. – J.R. Feb 9 '14 at 17:43

One proviso: You do need that $X$ is non-empty in the statement.

To elaborate on the hints you have been given; To prove existance, pick $x_0 \in X$, and call (for convenience of writing) $g(x_0) = x_1, g(x_1) = x_2$ etcetera. Let $d(x_0,x_1) = d$. Then $d(x_1,x_2) \leq \lambda d$, and $d(x_2,x_3) \leq \lambda^2 d$...can you see how to extend this to show that the sequence is Cauchy?

For uniqueness, suppose $x$ and $y$ are both fixed points. What is $d(g(x),g(y))$?.

• I don't think you do - if $x = y$ then both sides of the inequality are $0$, which is fine. – meta Feb 8 '14 at 19:37
• Touche! (I'm used to strong inequalities being used, which isn't really different here, and didn't notice the difference.) – Jonathan Y. Feb 8 '14 at 19:39
• @meta: After we got to $d(x_{n+1}, x_n) \le \lambda^n d(x_1, x_0)$, then assuming that $m > n$, $d(x_m, x_n) \le d(x_m, x_{m-1}) + d(x_{m-1}, x_{m-2}) + ... + d(x_{n+1}, x_{n})$ since each term of the right hand side is 0 ...so if we add up all the 0 terms, we get 0 on the right hand side. Therefore, $d(x_m, x_n)$ is 0. If this is right, then the question I have here is how do I guarantee that $x_{m-1} > x_n$? – afsdf dfsaf Feb 9 '14 at 3:04