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^{*})<d(x^{\prime% },x^{*}),$

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