5 Fractal Geometry
5.1 Natural Geometry, Self-similarity and Fractal Dimension
The objects of classical geometry (lines, curves, spheres, etc.) tend to seem flatter and less interesting
as one zooms in: at small scales, every differentiable curve looks like a line segment! By contrast,
real-world objects tend to exhibit greater detail at smaller scales. A seemingly spherical orange is
dimpled on closer inspection: is its surface area that of a sphere, or is the area greater due to the
dimples? What if we zoom in further? Under a microscope, the dimples in the orange are seen to
have minute cracks and fissures. With modern technology, we can ‘see’ almost to the molecular level;
what does surface area even mean at such a scale?
The Length of a Coastline In 1967 Benoit Mandelbrot asked a related question in a now-famous
paper, How Long Is the Coast of Britain? Statistical Self-Similarity and Fractional Dimension. His essential
point was that this question has no simple answer:
34
Should one measure by walking along the mean
high tide line? But where is this? Do we ‘walk’ round every pebble? Do we skirt every grain of sand?
Every molecule? As the scale of consideration shrinks, the measured length becomes absurdly large.
Here is a sketch of Mandelbrot’s approach.
35
• Given a ruler of length R, let N be the number required to trace round the coastline when laid
end-to-end.
• Plot log N against log(1/R) for several sizes of ruler. The data suggests a straight line!
log N ≈ log k + D log(1/R) = log(kR
−D
) =⇒ N ≈ kR
−D
The number D is Mandelbrot’s fractal dimension of the coastline.
This notion of fractal dimension is purely empirical, though it does seem to capture something about
the ‘roughness’ of a coastline: the bumpier the coast, the greater its fractal dimension. For mainland
Britain with its smooth east and rugged west coasts D ≈ 1.25. Given its many fjords, Norway has a
far rougher coastline and thus a higher fractal dimension D ≈ 1.52.
Example 5.1. As a sanity check, consider a smooth circular ‘coastline.’
Approximate the circumference using N rulers of length R: clearly
R = 2 sin
π
N
As N → ∞, the small angle approximation for sine applies,
R ≈
2π
N
=⇒ N ≈ 2π R
−1
1
R
2π
N
where the approximation improves as N → ∞. The fractal dimension of a circle is therefore D = 1.
The same analysis applies to any smooth curve (Exercise 3).
34
The official answer from the Ordnance Survey (the UK government mapping office) is, ‘It depends.’ The all-knowing
CIA states 7723 miles, though offers no evidence as to why.
35
For more detail see the Fractal Foundation’s website. Mandelbrot coined the word fractal, though he didn’t invent the
concept from nothing. Rather he applied earlier ideas of Hausdorff, Minkowski and others, and observed how the natural
world contains many examples of fractal structures.
81
Our goal is to describe a related notion of fractional dimension for self-similar objects. To help moti-
vate the definition, recall some of the standard objects of pre-fractal geometry.
Segment A segment can be viewed as N copies of itself each scaled by a
factor r =
1
N
.
Square A square comprises N copies of itself scaled by a factor r =
1
√
N
.
Cube A cube comprises N copies of itself scaled by a factor r =
1
3
√
N
.
In each case observe that N =
1
r
D
where D is the usual dimension of the
object (1, 2 or 3). Inspired by this, we make a loose definition.
Definition 5.2. A geometric figure is self-similar if it may be subdivided into N similar copies of
itself, each scaled by a magnification factor r < 1. The fractal dimension of such a figure is
D := log
1/r
N =
log N
log( 1/r)
= −
log N
log r
Example 5.3. The botanical pictures below offer some evidence for non-integer fractal dimension
and for the idea that self-similarity is a natural phenomenon. The ‘tree’ comprises N = 3 copies of
itself, each scaled by r = 0.4. Its fractal dimension is therefore D = −
log 3
log 0.4
≈ 1.199.
The fern has N = 7 and r = 0.3 for a fractal dimension D = −
log 7
log 0.3
≈ 1.616.
Tree fractal D ≈ 1.199 Fern fractal D ≈ 1.616
With dimensions between 1 and 2, both objects exhibit an intuitive idea of fractal dimension: both
seem to occupy more space than mere lines, but neither has positive area. Moreover, the fern seems
to occupy more space—has higher dimension—than the tree. (The ‘trunk’ and ‘branches’ in the first
picture aren’t really part of the fractal and are drawn only to give the picture a skeleton.)
82
Example 5.4 (Cantor’s Middle-third Set). This famous example dates from the late 1800s.
36
Starting with the unit interval C
0
= [0, 1], define a se-
quence of sets ( C
n
) where C
n+1
is obtained by deleting the
open ‘middle-third’ of each interval in C
n
; for instance
C
1
=
0,
1
3
∪
2
3
, 1
Cantor’s set is essentially the limit of this sequence:
C :=
∞
\
n=0
C
n
0
1
3
2
3
1
C
0
C
1
C
2
C
3
.
.
.
Cantor’s set has several strange properties, none of which we establish rigorously.
Zero length The sum of the lengths of the disjoint sub-intervals comprising C
n
is length(C
n
) =
2
3
n
since we delete
1
3
of the remaining set at each step. It follows that
∀n ∈ N
0
, length(C) ≤
2
3
n
=⇒ length(C) = 0
We conclude that C contains no subintervals!
Uncountability There exists a bijection between C and the original interval [0, 1]! (This issue is of
limited interest to us, though you’ve likely encountered the notion elsewhere.)
Self-similarity Since C
n+1
consists of two copies of C
n
, each shrunk by a factor of
1
3
and one shifted
2
3
to the right, we abuse notation slightly to write
C
n+1
=
1
3
C
n
∪
1
3
C
n
+
2
3
‘Taking limits,’ Cantor’s set is seen to comprise two shrunken copies of itself:
C =
1
3
C ∪
1
3
C +
2
3
In particular, its fractal dimension is D =
log 2
log 3
≈ 0.631.
The Cantor set has many generalizations:
• Removing different fractions of every interval at each stage produces sets with other fractal
dimensions. For instance, removing the 2
nd
and 4
th
fifths results in D =
log 3
log 5
≈ 0.683.
• Higher-dimensional analogues include the Sierpi
´
nski triangle (D =
log 3
log 2
≈ 1.585) and carpet
(Example 5.10.3, D =
log 8
log 3
≈ 1.893), and the Menger sponge (D =
log 20
log 3
≈ 2.727).
36
Henry Smith discovered this set in 1874 while investigating integrability (the ‘length’ of a set was later formalized using
measure theory). Cantor’s 1883 description focused on topological properties, with self-similarity being less of a concern.
83
Example 5.5 (The Koch Curve and Snowflake). Another generalization of the Cantor set is pro-
duced as the limit of a sequence of curves.
• Let K
0
be a segment of length 1.
• Replace the middle third of K
0
with the other two sides of
an equilateral triangle to create K
1
.
• Replace the middle third of each segment in K
1
as before to
create K
2
.
• Repeat ad infinitum.
The resulting curve is drawn along with the Koch snowflake ob-
tained by arranging three copies around an equilateral triangle.
The relation to the Cantor set should be obvious in the construc-
tion. Indeed if K
0
= [0, 1], then the intersection of this with the
Koch curve is the Cantor set itself!
The Koch curve is self-similar in that it comprises N = 4 copies
of itself shrunk by a factor of r =
1
3
. Its fractal dimension is
therefore
log 4
log 3
≈ 1.2619, between that of a line and an area.
We may also consider the curve’s length. Let s
n
be the number
of segments in K
n
, each having length t
n
, and let ℓ
n
= t
n
s
n
be the
length of the curve K
n
. It follows that
s
n
= 4
n
, t
n
=
1
3
n
=⇒ ℓ
n
=
4
3
n
→ ∞
The Koch curve is infinitely long!
Koch Curve
Koch Snowflake
Self-similarity
Exercises 5.1. 1. By removing a constant middle fraction of each interval, construct a fractal analo-
gous to the Cantor set but with dimension
1
2
. More generally, if one removes a constant middle
fraction f from each interval, what is the resulting dimension?
2. Prove that the area inside the n
th
iteration of the construction of the Koch snowflake is
A
n
=
√
3
4
1 +
3
5
1 −
4
9
n
−−−→
n→∞
2
√
3
5
=
8
5
Area(△)
3. Suppose r(t), t ∈ [0, 1] describes a regular (smooth) curve in the plane.
(a) Use the arc-length formula L =
R
1
0
|
r
′
(t)
|
dt together with Riemann sums and the linear
approximation r(t +
1
N
) ≈ r(t) +
1
N
r
′
(t) to argue that
L ≈
N−1
∑
k=0
r
k + 1
N
−r
k
N
(∗)
(b) Parametrizing r such that each segment in ( ∗) has the same length R, prove that L ≈ NR.
(Any regular curve thus has fractal dimension 1 in the sense stated by Mandelbrot (pg. 81))
84
5.2 Contraction Mappings & Iterated Function Systems
Thus far we have dealt informally with fractals where the whole consists of multiple pieces scaled
by the same factor. In general we can mix up scaling factors. To do this, and to be more rigorous, we
need to borrow some ideas from topology and analysis.
Definition 5.6. A contraction mapping with scale factor c ∈ [0, 1) is a function S : R
m
→ R
m
such that
∀x, y ∈ R
m
,
|
S(x) −S(y)
|
≤ c
|
x −y
|
A contraction mapping moves inputs closer together. It should be clear that every such is continuous
(lim x
n
= y =⇒ lim S(x
n
) = S(y)).
Example 5.7. The function S(x) =
1
3
x +
2
3
is a contraction mapping (on R) with scale factor c =
1
3
:
|
S(x) −S(y)
|
=
1
3
|
x −y
|
To motivate the key theorem, consider using S to inductively define a sequence: given any x
0
, define
x
n+1
:= S(x
n
)
The first few terms are
x
1
=
x
0
3
+
2
3
, x
2
=
x
0
3
2
+
2
3
2
+
2
3
, x
3
=
x
0
3
3
+
2
3
3
+
2
3
2
+
2
3
which suggests (geometric series)
x
n
=
x
0
3
n
+ 2
n
∑
k=1
1
3
k
=
x
0
3
n
+
2( 3
−1
−3
−n−1
)
1 −3
−1
= 1 +
1
3
n
(x
0
−1)
This can easily be verified by induction if you prefer. The striking thing about this sequence is that it
converges to the same limit lim x
n
= 1 regardless of the initial term x
0
!
The example illustrates one of the most powerful and useful theorems in mathematics.
Theorem 5.8 (Banach Fixed Point Theorem). Let S : R → R be a contraction mapping. Then:
1. S has a unique fixed point: some L ∈ R
m
such that S(L) = L.
2. If x
0
∈ R is any value, then the sequence defined iteratively by x
n+1
:= S(x
n
) converges to L.
In fact, as will be crucial momentarily, Banach’s result holds whenever S : H → H is a contraction
mapping on any complete metric space.
37
The main goal of this section is to use Banach’s result to
generate certain fractals via repeated application of contraction mappings to an initial shape. Our
motivating example already illustrates this. . .
37
Very loosely, a metric space is a set on which a sensible notion of distance can be defined: on R, for instance, the
distance between two points is d(x, y) =
|
x −y
|
. If you’ve done analysis you’ll be familiar with completeness: every Cauchy
sequence converges (in H).
85
Example (5.4, Cantor Set mk. II). The functions S
1
, S
2
: R → R where
S
1
(x) =
x
3
S
2
(x) =
x
3
+
2
3
are contraction mappings with scale factor c =
1
3
. More importantly, these functions define the Cantor
set: at each stage of its construction, we defined
C
n+1
:= S
1
(C
n
) ∪ S
2
(C
n
) (∗)
Indeed, the self-similarity of the Cantor set can be expressed in the same manner: C = S
1
(C) ∪S
2
(C).
Amazingly, it barely seems to matter what initial set C
0
is chosen. Originally we took C
0
= [0, 1] to
be the unit interval, but we could instead start with the singleton set C
0
= {0}: iterating (∗) produces
C
1
=
0,
2
3
, C
2
=
0,
2
9
,
2
3
,
8
9
, C
3
=
0,
2
27
,
2
9
,
8
27
,
2
3
,
20
27
,
8
9
,
26
27
, . . .
The first few iterations are drawn in the first picture below; it appears as if, in the limit, C
n
is becoming
the Cantor set. The second picture starts with a very different initial set C
0
= [0.2, 0.5] ∪ [0.6, 0.7];
iterating this also appears to produce the Cantor set!
0
1
3
2
3
1
C
0
C
1
C
2
C
3
C
4
C
5
C
6
.
.
.
0
1
3
2
3
1
0
1
3
2
3
1
C
0
C
1
C
2
C
3
C
4
C
5
C
6
.
.
.
0
1
3
2
3
1
It certainly appears as if the Cantor set is generated by the contraction maps S
1
, S
2
independently of
the initial data C
0
. Our main result shows in what sense this is true. Since this requires some heavy
lifting from topology and analysis, we provide only a synopsis.
• A subset K ⊂ R
m
is compact if it is closed (contains its boundary points) and bounded (K lies
within some ball centered at the origin). For instance, K = [0, 1] is a compact subset of R.
• The set of non-empty compact subsets of R
m
is a metric space H. This means that the distance
d(X, Y) between X, Y ∈ H may sensibly be defined, though it is a little tricky. . .
38
38
The distance function is the Hausdorff metric. Given Y ∈ H, and x ∈ R
n
, define d
Y
(x) = inf
y∈Y
||
x −y
||
to be the
distance from x to the ‘nearest’ point of Y. Define d
X
(y) similarly. The Hausdorff distance between X and Y is then
d(X, Y) := max
(
sup
x∈X
d
Y
(x), sup
y∈Y
d
X
(y)
)
Roughly speaking, find x ∈ X which is as far away (d
Y
(x)) as possible from anything in Y, and find y ∈ Y similarly; d(X, Y)
is the larger of these distances. Crucially, d(X, Y) = 0 ⇐⇒ X = Y.
86
• Since H is a metric space, we can discuss convergent sequences (K
n
) of compact sets
lim
n→∞
K
n
= K ⇐⇒ lim
n→∞
d(K
n
, K) = 0
It also makes sense to speak of Cauchy sequences in H. It may be proved that H is complete:
every Cauchy sequence (K
n
) ⊆ H converges to some K ∈ H.
• The main result is a corollary of Banach’s result (Theorem 5.8).
Theorem 5.9 (Iterated Function Systems). Let S
1
, . . . , S
n
be contraction mappings on R
m
with scale
factors c
1
, . . . , c
n
. Define
S : H → H by S(K) =
n
[
i=1
S
i
(K)
1. S is a contraction mapping on H with contraction factor c = max(c
1
, . . . , c
n
).
2. S has a unique fixed set F ∈ H given by F = lim
k→∞
S
k
(K
0
) for any non-empty K
0
∈ H.
Part 1 is not super difficult to prove if you’re willing to work with the definition of the Hausdorff
metric (try it if you’re comfortable with analysis!). Part 2 is Banach’s theorem.
The upshot is this: repeatedly applying contraction mappings to any non-empty compact set E pro-
duces a compact limit set which is independent of E! We call the limit F for fractal. Such fractals are
sometimes called attractors: being limit-sets, they ‘attract’ data towards themselves.
Examples 5.10. 1. (Example 5.4, mk.III) We revisit the Cantor set one last time.
The contractions S
1
(x) =
1
3
x and S
2
(x) =
1
3
x +
2
3
(on R) produce a contraction S : H → H:
S(K) :=
S
1
(x), S
2
(x) : x ∈ K
By Theorem 5.9, if C
0
⊂ R is non-empty closed and bounded, then C = lim S
n
(C
0
). Certainly
all three of our previous choices for C
0
are such sets: [0, 1], {0} and [0.2, 0.5] ∪[0.6, 0.7].
A nice application of the Theorem allows us to find all sorts of interesting points in the Cantor
set. For instance, consider the functions T, U, where
T(x) = S
1
S
2
(x)
=
x
9
+
2
9
and U(y) = S
2
S
1
(y)
=
y
9
+
2
3
These are contractions on R (c =
1
9
) whose unique fixed points are t =
1
4
and u =
3
4
; moreover
S
1
(u) = t and S
2
(t) = u. Now consider the non-empty compact set K = {t, u} ∈ H. Plainly
S(K) =
S
1
(t), S
1
(u), S
2
(t), S
2
(u)
=
1
12
,
1
4
,
3
4
,
11
12
⊃ K
0
1
3
2
3
1
1
4
3
4
S
2
(
1
4
) =
3
4
S
1
(
3
4
) =
1
4
It follows (induction) that K ⊆ lim S
n
(K) = C: both t =
1
4
and u =
3
4
lie in the Cantor set!
This seems paradoxical:
1
4
does not lie at the end of any deleted interval (all such points have
denominator 3
n
) but yet the Cantor set contains no intervals. How does
1
4
end up in there?!
87
2. (Example 5.5) The Koch curve arises from four contraction mappings S
i
: R
2
→ R
2
, each with
scale factor c =
1
3
.
Mapping Effect
S
1
(x, y) =
x
3
,
y
3
Scale
1
3
S
2
(x, y) =
1
6
x −
√
3
6
y +
1
3
,
√
3
6
x +
1
6
y
Scale
1
3
, rotate 60°, translate
S
3
(x, y) =
1
6
x +
√
3
6
y +
1
2
,
√
3
6
x −
1
6
y +
√
3
6
Scale
1
3
, rotate −60°, translate
S
4
(x, y) =
x
3
+
2
3
,
y
3
Scale
1
3
, translate
The combined map
S(K) := S
1
(K) ∪S
2
(K) ∪S
3
(K) ∪S
4
(K)
is a contraction on H = {non-empty compact K ⊂ R
2
}.
Regardless of the initial input K
0
∈ H, the limit lim S
n
(K
0
) is the Koch curve: applied to the
entire curve (drawn), the image of each S
i
is colored. The picture moreover links to a series of
animated constructions starting with different initial sets K
0
.
We can also play a similar game to the previous example to find interesting points on the curve.
For instance, the unique fixed point (
51
146
,
3
√
3
146
) of U = S
2
◦S
1
lies on the curve!
3. The Sierpi
´
nski carpet may be constructed using eight contraction
mappings, each of which scales the whole picture by a (length-scale)
factor of c =
1
3
, for a dimension of D =
log 8
log 3
≈ 1.893.
As with the Koch curve, the image links to several alternative con-
structions using different initial sets K
0
.
4. This fractal fern is constructed using three contraction mappings:
S
1
: Scale by
3
4
, rotate 5° clockwise, and translate by (0,
1
4
)
S
2
: Scale by
1
4
, rotate 60° counter-clockwise, and translate by (0,
1
4
)
S
3
: Scale by
1
4
, rotate 60° clockwise, and translate by (0,
1
4
)
The linked animation shows the first few steps of its contsruction
starting from a single vertical line segment K
0
.
88
Fractal Dimension Revisited
Since Theorem 5.9 permits several different contraction factors, we need a new
approach to fractal dimension. We ask how many disks of a given radius ϵ are
required to cover a set. In the picture, the unit square requires four disks of
radius ε = 0.4. For smaller ε, we plainly need more disks. . .
Definition 5.11. Let K be a compact subset of R
m
.
1. If ε > 0, the closed ε-ball centered at x ∈ K consists of the points at most a distance ε from x:
B
ϵ
(x) = {y ∈ R
m
: d(x, y) ≤ ε}
2. The minimal ε-covering number for K is the smallest number of radius-ϵ balls needed to cover K:
N(K, ε) = min
(
M : ∃x
1
, . . . , x
M
∈ K with K ⊆
M
[
n=1
B
ϵ
(x
n
)
)
3. The fractal dimension of K is the limit
D = lim
ε→0
log N(K, ε)
log( 1/ε)
Rigorously proving that N and D exist requires a more thorough study of topology, though a simple
example should at least convince us that the definition is reasonable!
Example 5.12. Let K = [0, 1] be the interval of length 1. It is not hard to check that
ε ≥
1
2
⇐⇒ N(K, ε) = 1 and
1
4
≤ ε <
1
2
⇐⇒ N(K, ε) = 2
etc. More generally, N and ϵ are related via
1
2N
≤ ϵ <
1
2(N −1)
The dimension of K (= 1) may therefore be recovered via the squeeze theorem
D = lim
ϵ→0
log N
log( 1/ε)
= 1
Thankfully an easier-to-visualize modification is available using boxes.
Theorem 5.13 (Box-counting). Let K ⊂ R
m
be compact and cover R
m
by boxes of side length
1
2
n
. Let
N
n
(K) be the number of such boxes intersecting K. Then
D = lim
n→∞
log N
n
(K)
log 2
n
89
We finish with a formula satisfied by the dimension of an iterated function system (Theorem 5.9).
Theorem 5.14. Let {S
n
}
M
n=1
be an iterated function system with attractor (limiting fractal) F and
where each contraction S
n
has scale factor c
n
∈ (0, 1). Under reasonable conditions,
39
the fractal
dimension is the unique real number D satisfying
M
∑
n=1
c
D
n
= 1
Examples 5.15. 1. We easily recover Definition 5.2 when the scale-factors are identical c
n
= r:
Mr
D
= 1 =⇒ D =
−log M
log r
=
log M
log( 1/r)
2. The fractal fern (Examples 5.10) is generated by three contraction maps with scale factors
3
4
,
1
4
,
1
4
.
Its dimension is the solution to the equation
3
4
D
+
1
4
D
+
1
4
D
= 1 =⇒ D ≈ 1.3267
3. Numerical approximation is usually required to find D, though sometimes an exact solution is
possible. For instance, if c
1
= c
2
=
1
2
and c
3
= c
4
= c
5
=
1
4
, then
2
1
2
D
+ 3
1
4
D
= 1
This is quadratic in α =
1
2
D
, whence
2α + 3α
2
= 1 =⇒ α =
1
3
=⇒ D = log
2
3 ≈ 1.584
Other methods of creating fractals
The contraction mapping approach is one of many ways to cre-
ate fractals. Two other famous examples are the logistic map
(related to numerical approximations to non-linear differential
equations) and the Mandelbrot set (pictured).
The Mandelbrot set arises from a construction in the complex
plane. For a given c ∈ C, we iterate the function
f
c
(z) = z
2
+ c
If f ( f ( f (··· f (c) ···))) remains bounded, no matter how many
times f is applied, then c lies in the Mandelbrot set.
Much better pictures and trippy videos can be found online. . .
−1
i
−i
39
Roughly: the outputs of each S
n
meet only at boundary points; the ‘pieces’ of the fractal cannot overlap too much.
90
Exercises 5.2. 1. Let S
1
(x) =
1
3
x and S
2
(x) =
1
3
x +
2
3
be the contraction mappings defining the
Cantor set and suppose x, y, z ∈ R satisfy
y = S
1
(x), z = S
2
(y), x = S
2
(z)
Show that x, y, z lie in the Cantor set, and find their values.
2. (a) As in Example 5.7, illustrate Banach’s theorem for the contraction S(x) =
1
2
x + 5.
(b) Repeat part (a) for any linear polynomial S(x) = cx + d where
|
c
|
< 1.
3. Verify the claim in Example 5.10.2 that the point (
51
146
,
3
√
3
146
) lies on the Koch curve.
4. The construction of a Cantor-type set starts by removing the open intervals (0.1, 0.2) and
(0.6, 0.8) from the unit interval.
(a) Sketch the first three iterations of this fractal.
(b) This construction may be described using three contraction mappings; what are they?
(c) State an equation satisfied by the dimension D of the set and use a computer algebra
package to estimate its value.
5. A variation on the Koch curve is constructed using five contraction mappings. Each scales the
whole picture by a factor c, then rotates counter-clockwise, before finally translating.
map scale rotate translate (add (x, y))
S
1
1
2
0 0
S
2
1
4
90° (
1
2
, 0)
S
3
1
4
0 (
1
2
,
1
4
)
S
4
1
4
−90° (
3
4
,
1
4
)
S
5
1
4
0 (
3
4
, 0)
(a) Suppose your initial set K
0
is the straight line segment from (0, 0) to (1, 0). Draw the first
two iterations of the fractal’s construction.
(b) The dimension of the fractal is the solution D to (
1
2
)
D
+ (
1
4
)
D
+ (
1
4
)
D
+ (
1
4
)
D
+ (
1
4
)
D
= 1.
By observing that
1
4
=
1
2
2
, convert to a quadratic equation in the variable α = (
1
2
)
D
.
Hence compute the dimension of the fractal.
(c) The dimension of the fractal is larger than that of the Koch curve
log 4
log 3
. Explain (infor-
mally) what this means.
6. Verify the details of Example 5.12, including the computation of the limit.
7. Given constants 0 ≤ c
1
, . . . , c
n
< 1, use calculus to prove that the function f (x) =
∑
c
x
i
is strictly
decreasing. Hence conclude that the value D in Theorem 5.14 exists and is unique.
8. (If you’ve done analysis) Let S : R → R be a contraction mapping with scale factor c, suppose
x
0
∈ R is given, and define x
n+1
:= S(x
n
) inductively. Prove:
∀k, n ≥ 0,
|
x
n+k
− x
n
|
<
c
n
1 − c
|
x
1
− x
0
|
Conclude that the sequence (x
n
) is Cauchy. Hence prove Banach’s Theorem (5.8).
91
