Statement and Proof

Statement of the theorem

Banach fixed-point theorem. Let $X$ be a closed, nonempty subset of $\mathbb{R}$, and $f : X \to X$ a $k$-contracting mapping, with $0 \leq k < 1$. Then $f$ has a unique fixed point $c$ in $X$, and for every $u_0$ in $X$, the sequence defined by $u_{n+1} = f(u_n)$ converges to $c$.

Three hypotheses, none superfluous: $X$ closed — a segment $[a \,;\, b]$ does the job perfectly —, stability $f(X) \subset X$, and strict contraction $k < 1$.

Banach's statement, published in 1922, actually holds in any complete metric space, which makes it one of the most widely reused tools in analysis.

Proof

Existence. Start from an arbitrary point $u_0$ of $X$ and set $u_{n+1} = f(u_n)$; stability $f(X) \subset X$ guarantees that the sequence remains well defined in $X$.

Applying the contraction property to two consecutive terms gives

$$\lvert u_{n+1} - u_n \rvert = \lvert f(u_n) - f(u_{n-1}) \rvert \leq k\,\lvert u_n - u_{n-1} \rvert$$

hence, by induction, $\lvert u_{n+1} - u_n \rvert \leq k^n\,\lvert u_1 - u_0 \rvert$.

For $p > n$, the triangle inequality and the sum of a geometric series then give

$$\lvert u_p - u_n \rvert \leq \sum_{j=n}^{p-1} \lvert u_{j+1} - u_j \rvert \leq \lvert u_1 - u_0 \rvert \sum_{j=n}^{p-1} k^j \leq \frac{k^n}{1 - k}\,\lvert u_1 - u_0 \rvert$$

The upper bound tends to $0$ as $n$ tends to infinity, independently of $p$: the sequence $(u_n)$ is Cauchy. Since $\mathbb{R}$ is complete, it converges to a real number $c$, and since $X$ is closed, $c$ belongs to $X$.

A contraction mapping being continuous, taking the limit in $u_{n+1} = f(u_n)$ gives $c = f(c)$.

Uniqueness. Suppose there are two fixed points $c$ and $d$. Then

$$\lvert c - d \rvert = \lvert f(c) - f(d) \rvert \leq k\,\lvert c - d \rvert$$

so $(1 - k)\,\lvert c - d \rvert \leq 0$. Since $1 - k > 0$, it follows that $\lvert c - d \rvert = 0$, that is, $c = d$.

Every hypothesis is necessary

Hypothesis removed	Counterexample	What fails
$X$ closed	$f(x) = \dfrac{x}{2}$ on $\left]0 \,;\, 1\right]$	the limit $0$ leaves $X$
$f(X) \subset X$	$f(x) = \dfrac{x}{2} + 3$ on $[0 \,;\, 1]$	the sequence leaves the interval
strict $k < 1$	$f(x) = x + \dfrac{1}{x}$ on $\left[1 \,;\, +\infty\right[$	no fixed point
$X$ nonempty	—	nothing to prove

Classic pitfall

Forgetting to check stability $f(X) \subset X$. It is the step people most readily skip, and yet it is the one that requires the real work in an exercise: you must establish bounds on $f$ over $X$, often through a study of its variations. Without it, the sequence of iterates is not even defined.