proof of Banach fixed point theorem

Let $(X,d)$ be a non-empty, complete metric space, and let $T$ be acontraction 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 thatfor 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$

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

$=$${\displaystyle \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 forall $n\ge 0$.

Given any $ϵ>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$ (wemay 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)$ iscomplete, this implies that the sequence has a limit in $(X,d)$;define $x^{*}$ to be this limit. We now prove that $x^{*}$ is a fixedpoint of $T$. Suppose it is not, then $\delta :=d(T{x}^{*},x^{*})>0$.However, because $(x_n)$ converges to $x^{*}$, there is a naturalnumber $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$.