# proof of Banach fixed point theorem

Let $(X,d)$ be a non-empty, complete metric space, and let $T$ be a
contraction mapping on $(X,d)$ with constant $q$. Pick an arbitrary
${x}_{0}\in X$, and define the sequence ${({x}_{n})}_{n=0}^{\mathrm{\infty}}$ by
${x}_{n}:={T}^{n}{x}_{0}$. Let $a:=d(T{x}_{0},{x}_{0})$. We first show by induction^{} that
for any $n\ge 0$,

$$d({T}^{n}{x}_{0},{x}_{0})\le \frac{1-{q}^{n}}{1-q}a.$$ |

For $n=0$, this is obvious. For any $n\ge 1$, suppose that $d({T}^{n-1}{x}_{0},{x}_{0})\le \frac{1-{q}^{n-1}}{1-q}a$. Then

$d({T}^{n}{x}_{0},{x}_{0})$ | $\le $ | $d({T}^{n}{x}_{0},{T}^{n-1}{x}_{0})+d({x}_{0},{T}^{n-1}{x}_{0})$ | ||

$\le $ | ${q}^{n-1}d(T{x}_{0},{x}_{0})+{\displaystyle \frac{1-{q}^{n-1}}{1-q}}a$ | |||

$=$ | $\frac{{q}^{n-1}-{q}^{n}}{1-q}}a+{\displaystyle \frac{1-{q}^{n-1}}{1-q}}a$ | |||

$=$ | $\frac{1-{q}^{n}}{1-q}}a$ |

by the triangle inequality^{} and repeated application of the property
$d(Tx,Ty)\le qd(x,y)$ of $T$. By induction, the inequality^{} holds for
all $n\ge 0$.

Given any $\u03f5>0$, it is possible to choose a natural number^{} $N$
such that $$ for all $n\ge N$, because
$\frac{{q}^{n}}{1-q}a\to 0$ as $n\to \mathrm{\infty}$. Now, for any $m,n\ge N$ (we
may assume that $m\ge n$),

$d({x}_{m},{x}_{n})$ | $=$ | $d({T}^{m}{x}_{0},{T}^{n}{x}_{0})$ | ||

$\le $ | ${q}^{n}d({T}^{m-n}{x}_{0},{x}_{0})$ | |||

$\le $ | ${q}^{n}{\displaystyle \frac{1-{q}^{m-n}}{1-q}}a$ | |||

$$ | $$ |

so the sequence $({x}_{n})$ is a Cauchy sequence^{}. Because $(X,d)$ is
complete^{}, this implies that the sequence has a limit in $(X,d)$;
define ${x}^{*}$ to be this limit. We now prove that ${x}^{*}$ is a fixed
point^{} of $T$. Suppose it is not, then $\delta :=d(T{x}^{*},{x}^{*})>0$.
However, because $({x}_{n})$ converges^{} to ${x}^{*}$, there is a natural
number $N$ such that $$ for all $n\ge N$. Then

$d(T{x}^{*},{x}^{*})$ | $\le $ | $d(T{x}^{*},{x}_{N+1})+d({x}^{*},{x}_{N+1})$ | ||

$\le $ | $qd({x}^{*},{x}_{N})+d({x}^{*},{x}_{N+1})$ | |||

$$ | $\delta /2+\delta /2=\delta ,$ |

contradiction^{}. So ${x}^{*}$ is a fixed point of $T$. It is also unique.
Suppose there is another fixed point ${x}^{\prime}$ of $T$; because ${x}^{\prime}\ne {x}^{*}$, $d({x}^{\prime},{x}^{*})>0$. But then

$$ |

contradiction. Therefore, ${x}^{*}$ is the unique fixed point of $T$.

Title | proof of Banach fixed point theorem |
---|---|

Canonical name | ProofOfBanachFixedPointTheorem |

Date of creation | 2013-03-22 13:08:34 |

Last modified on | 2013-03-22 13:08:34 |

Owner | asteroid (17536) |

Last modified by | asteroid (17536) |

Numerical id | 5 |

Author | asteroid (17536) |

Entry type | Proof |

Classification | msc 54A20 |

Classification | msc 47H10 |

Classification | msc 54H25 |