= Solution
The <contraction mapping theorem> states that a self-map $f$ of a nonempty <complete metric space> $(X,d)$ satisfying $d(fu,fv)\le qd(u,v)$ for a fixed $0\le q<1$ has a unique <fixed point>. Its iterates converge to that point from every starting point.
To prove it, set $u_{n+1}=f(u_n)$. Induction gives $d(u_{n+1},u_n)\le q^n d(u_1,u_0)$. Hence for $m>n$, the <triangle inequality> yields
$$
d(u_m,u_n)\le\sum_{j=n}^{m-1}q^j d(u_1,u_0)\le\frac{q^n}{1-q}d(u_1,u_0).
$$
Thus the iterates are a <Cauchy sequence>, with limit $u$ by completeness. The contraction inequality gives $d(fu,u)\le qd(u,u_n)+d(u_{n+1},u)\to0$, so $f(u)=u$. For any two fixed points $u,v$, $d(u,v)\le qd(u,v)$ forces equality of the points. This proves existence, uniqueness and convergence; passing $m\to\infty$ also gives the displayed error bound.
For the three-point example, positivity and symmetry of $d'$ are immediate. For three distinct points, the largest side has length two, no more than the sum of the other two; repeated-point triangle inequalities are trivial. Thus $d'$ is a <metric>. The <discrete metric> satisfies
$$
\boxed{d\le d'\le2d,}
$$
which proves <bilipschitz equivalence> of the two metrics. Define
$$
\boxed{f(x)=y,\qquad f(y)=f(z)=z.}
$$
The ratios of output to input distances for the three distinct pairs are $1/2,1/2,0$ in $d'$, so it is a contraction with $q=1/2$. In $d$, the pair $(x,y)$ has input and output distance one, precluding any $q<1$. This illustrates the <contraction property under equivalent metrics>.
Back to article page
