Math 104–Spring 2005–AndersonLecture Notes on Contraction Mapping TheoremDefinition 0.1 Let (S, d) be a metric space. A function f :S → S is a contraction if∃α ∈ [0, 1) ∀x, y ∈ Sd(f(x),f(y)) ≤ αd(x, y)s is a fixed point of f if f(s)=s.Theorem 0.2 (Contraction Mapping Theorem) If (S, d) isa complete metric space, and f : S → S is a contraction, thenf has a unique fixed point.Proof: We first show that a fixed point exists. Since S = ∅,we may choose an arbitrary s0∈ S. Consider the sequence (sn)defined bys1= f(s0)s2= f(s1)...sn+1= f(sn)If s1= s0,thenf(s0)=s1= s0,sos0is a fixed point.If s1= s0, w e claim thatd(sn+1,sn) ≤ αnd(s1,s0)The proof of the claim is by induction. Note thatd(s2,s1)=d(f(s1),f(s0))≤ αd(s1,s0)1Now suppose that d(sn+1,sn) ≤ αnd(s1,s0). Thend(sn+2,sn+1)=d(f(sn+1),f(sn))≤ αd(sn+1,sn)≤ α · αnd(s1,s0)= αn+1d(s1,s0)so the claim follows by induction.Next, we show that (sn) is a Cauchy sequence. Let ε>0.Since 0 <α<1, limn→∞αn= 0 by Example 9.7(b). Choose Nsuch thatαN<ε(1 − α)d(s1,s0)If m ≥ n>N,d(sm,sn) ≤ d(sm,sm−1)+···+ d(sn+1,sn)<αm−1d(s1,s0)+αm−2d(s1,s0)+···+ αnd(s1,s0)=1 − αm1 − α−1 − αn1 − αd(s1,s0) (by Exercise 9.18)=αn− αm1 − αd(s1,s0)<αn1 − αd(s1,s0)<αN1 − αd(s1,s0)<εso (sn)isCauchy.Since (S, d) is comp lete, ( sn) has a limit s ∈ S. We will showthat f (s)=s.Fixε>0. There exists N1such thatn>N1⇒ d(sn,s) <ε22Since (sn)isCauchy,thereexistsN2such thatn>N2⇒ d(sn+1,sn) <ε2Choose any n>max{N1,N2}.Thend(s, f(s)) ≤ d(s, sn+1)+d(sn+1,f(s))= d(s, sn+1)+d(f( sn),f(s))<ε2+ αd(sn,s)<ε2+ε2= εSince ε is arbitrary, d(s, f(s)) = 0, so f(s)=s.Thus,f has afixed point.To show the fixed point is unique, suppose f(s)=s andf( t)=t.Thend(s, t)=d(f(s),f(t))≤ αd(s, t)so(1 − α)d(s, t) ≤ 0so d(s, t) ≤ 0. Since d is a metric, d(s, t) = 0, and thus s = t,sothe fixed point is