# 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}^{\infty}$ by $x_{n}:=T^{n}x_{0}$. Let $a:=d(Tx_{0},x_{0})$. We first show by induction that for any $n\geq 0$,

 $d(T^{n}x_{0},x_{0})\leq\frac{1-q^{n}}{1-q}a.$

For $n=0$, this is obvious. For any $n\geq 1$, suppose that $d(T^{n-1}x_{0},x_{0})\leq\frac{1-q^{n-1}}{1-q}a$. Then

 $\displaystyle d(T^{n}x_{0},x_{0})$ $\displaystyle\leq$ $\displaystyle d(T^{n}x_{0},T^{n-1}x_{0})+d(x_{0},T^{n-1}x_{0})$ $\displaystyle\leq$ $\displaystyle q^{n-1}d(Tx_{0},x_{0})+\frac{1-q^{n-1}}{1-q}a$ $\displaystyle=$ $\displaystyle\frac{q^{n-1}-q^{n}}{1-q}a+\frac{1-q^{n-1}}{1-q}a$ $\displaystyle=$ $\displaystyle\frac{1-q^{n}}{1-q}a$

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

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

 $\displaystyle d(x_{m},x_{n})$ $\displaystyle=$ $\displaystyle d(T^{m}x_{0},T^{n}x_{0})$ $\displaystyle\leq$ $\displaystyle q^{n}d(T^{m-n}x_{0},x_{0})$ $\displaystyle\leq$ $\displaystyle q^{n}\frac{1-q^{m-n}}{1-q}a$ $\displaystyle<$ $\displaystyle\frac{q^{n}}{1-q}a<\epsilon,$

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(Tx^{*},x^{*})>0$. However, because $(x_{n})$ converges to $x^{*}$, there is a natural number $N$ such that $d(x_{n},x^{*})<\delta/2$ for all $n\geq N$. Then

 $\displaystyle d(Tx^{*},x^{*})$ $\displaystyle\leq$ $\displaystyle d(Tx^{*},x_{N+1})+d(x^{*},x_{N+1})$ $\displaystyle\leq$ $\displaystyle qd(x^{*},x_{N})+d(x^{*},x_{N+1})$ $\displaystyle<$ $\displaystyle\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}\neq x^{*}$, $d(x^{\prime},x^{*})>0$. But then

 $d(x^{\prime},x^{*})=d(Tx^{\prime},Tx^{*})\leq qd(x^{\prime},x^{*})

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

Title proof of Banach fixed point theorem ProofOfBanachFixedPointTheorem 2013-03-22 13:08:34 2013-03-22 13:08:34 asteroid (17536) asteroid (17536) 5 asteroid (17536) Proof msc 54A20 msc 47H10 msc 54H25