10.1. METRIC SPACES 255

10.1.7 Lipschitz Continuity and Contraction MapsThe following is of more interest in the case of normed vector spaces, but there is no harmin stating it in this more general setting. You should verify that the functions described inthe following definition are all continuous.

Definition 10.1.40 Let f : X→Y where (X ,d) and (Y,ρ) are metric spaces. Then f is saidto be Lipschitz continuous if for every x, x̂ ∈ X , ρ ( f (x) , f (x̂)) ≤ rd (x, x̂). The function iscalled a contraction map if r < 1.

The big theorem about contraction maps is the following.

Theorem 10.1.41 Let f : (X ,d)→ (X ,d) be a contraction map and let (X ,d) be a completemetric space. Thus Cauchy sequences converge and also d ( f (x) , f (x̂)) ≤ rd (x, x̂) wherer < 1. Then f has a unique fixed point. This is a point x ∈ X such that f (x) = x. Also, if x0is any point of X , then

d (x,x0)≤d (x0, f (x0))

1− rAlso, for each n,

d ( f n (x0) ,x0)≤d (x0, f (x0))

1− r,

and x = limn→∞ f n (x0).

Proof: Pick x0 ∈ X and consider the sequence of iterates of the map,

x0, f (x0) , f 2 (x0) , · · · .

We argue that this is a Cauchy sequence. For m < n, it follows from the triangle inequality,

d ( f m (x0) , f n (x0))≤n−1

∑k=m

d(

f k+1 (x0) , f k (x0))≤

∞

∑k=m

rkd ( f (x0) ,x0)

The reason for this last is as follows.

d(

f 2 (x0) , f (x0))≤ rd ( f (x0) ,x0)

d(

f 3 (x0) , f 2 (x0))≤ rd

(f 2 (x0) , f (x0)

)≤ r2d ( f (x0) ,x0)

and so forth. Therefore,

d ( f m (x0) , f n (x0))≤ d ( f (x0) ,x0)rm

1− r

which shows that this is indeed a Cauchy sequence. Therefore, there exists x such that

limn→∞

f n (x0) = x

By continuity,f (x) = f

(limn→∞

f n (x0))= lim

n→∞f n+1 (x0) = x.