CorollaryStatement: AI-adaptedProof: AI-generatedSession-authored (Fable 5 assisted)precheck passjudge pass (z-ai/glm-5.2)audited 2026-07-27

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

The a priori bound $d(x^{}, x_n) \le q^n d(x_1,x_0)/(1-q)$ and the a posteriori bound $d(x^{}, x_{n+1}) \le q\,d(x_{n+1},x_n)/(1-q)$

Statement

Let $(X,d)$ be a nonempty complete metric space, let $f : X \to X$ be a contraction with constant $q$ , $0 \le q < 1$ (Lipschitz map, $\alpha$ -Hölder map for rational $0 < \alpha \le 1$ , and contraction), let $x_0 \in X$ , let $x_{n+1} := f(x_n)$ be the iterates, and let $x^{*}$ be the unique fixed point of $f$ , so that $x^{*} = \lim_{n} x_n$ (A contraction of a nonempty complete metric space into itself has exactly one fixed point, the limit of the iterates from any starting point, A sequence in a metric space has at most one limit). Then for every $n \in \mathbb{N}$ :

A priori bound. $d(x^{*}, x_n) \;\le\; \frac{q^{\,n}\, d(x_1,x_0)}{1-q}.$
A posteriori bound. $d(x^{*}, x_{n+1}) \;\le\; \frac{q\, d(x_{n+1}, x_n)}{1-q}.$

The first bound is computable before the iteration is run, from the first step alone; the second uses the step just taken and is therefore sharper in practice.

Facts & Assumptions

Given: A nonempty complete metric space $(X,d)$ , a contraction $f : X \to X$ with constant $q$ satisfying $0 \le q < 1$ , a starting point $x_0 \in X$ , its iterates $x_{n+1} = f(x_n)$ , and the unique fixed point $x^{*}$ of $f$ ; write $C := d(x_1,x_0)/(1-q)$ .

[A1]

Banach's theorem: $f$ has exactly one fixed point $x^{*}$ , the iterates from any starting point converge to it, and $d(x_m,x_n) \le q^{\,n} d(x_1,x_0)/(1-q)$ for all $m \ge n$ (A contraction of a nonempty complete metric space into itself has exactly one fixed point, the limit of the iterates from any starting point).

[L1]

Reverse triangle inequality: $|d(u,w) - d(v,w)| \le d(u,v)$ in any metric space (The reverse triangle inequality $|d(x,z) - d(y,z)| \le d(x,y)$ in any metric space).

[L2]

Convergence in $(X,d)$ means $d(x_m, x^{*}) \to 0$ in $\mathbb{R}$ ; limits in a metric space are unique, which licenses the notation $\lim_n x_n$ for a sequence already known to converge (Convergence of a sequence in a metric space: $x_k \to x$ iff $d(x_k, x) \to 0$ in $\mathbb{R}$ , A sequence in a metric space has at most one limit, Limits and Cauchy sequences of reals).

[L3]

Limits of reals preserve non-strict inequalities holding eventually, a constant sequence converges to that constant, and the limit of a real sequence is unique (Limits preserve non-strict inequalities, A sequence has at most one limit).

[L4]

Recursion determines a sequence from its starting point and the map (The recursion theorem), and induction on $\mathbb{N}$ (The principle of mathematical induction).

[L5]

$1 - q > 0$ , so $1/(1-q) > 0$ ; $q^{\,1} = q$ ; and metrics are nonnegative (Inverses of positives are positive, and reciprocation reverses order, Integer powers $a^m$ , Nonnegativity of a metric is a consequence of the other axioms, not an axiom, Metric space: $d(x,y) = 0$ iff $x = y$ , symmetry, and the triangle inequality; pseudometric and ultrametric).

Proof

technique · direct

1.1

Fix $n \in \mathbb{N}$ . By [A1] the iterates converge to $x^{*}$ , so $d(x_m,x^{*}) \to 0$ as $m$ grows.

A1L2

1.2

Fix $n$ and consider the iterates of $f$ started at $y_0 := x_n$ . By uniqueness in the recursion theorem, $y_j = x_{n+j}$ for every $j$ , since both sides start at $x_n$ and both satisfy the recursion $u_{j+1} = f(u_j)$ ; in particular $y_1 = x_{n+1}$ .

2.1

By [L1], $|d(x_m,x_n) - d(x^{*},x_n)| \le d(x_m,x^{*})$ for every $m$ , so the real sequence $\big(d(x_m,x_n)\big)_{m}$ converges, and $\lim_{m} d(x_m,x_n) = d(x^{*},x_n)$ .

step 1.1L1L3

3.1

By [A1], $d(x_m,x_n) \le q^{\,n} C$ for every $m \ge n$ , that is eventually in $m$ ; the constant sequence with value $q^{\,n} C$ converges to $q^{\,n} C$ , so passing to the limit gives $d(x^{*},x_n) \le q^{\,n} C$ , which is claim 1.

step 2.1A1L3L5

4.1

The fixed point of $f$ does not depend on the starting point, by uniqueness in [A1], so claim 1 applied to the sequence $(y_j)$ at index $1$ reads $d(x^{*}, y_1) \le q^{\,1} d(y_1,y_0)/(1-q)$ .

step 3.1step 1.2A1L5

5.1

Substituting $y_1 = x_{n+1}$ and $y_0 = x_n$ gives $d(x^{*},x_{n+1}) \le q\,d(x_{n+1},x_n)/(1-q)$ , which is claim 2; claim 1 is step 3.1.

step 3.1step 1.2step 4.1∎

Remarks

The a posteriori bound is the a priori bound restarted. Nothing new is proved in steps 1.2, 4.1 and 5.1: the iteration is simply begun again at $x_n$ , which is legitimate because Banach's theorem holds from any starting point and its fixed point is the same one. That is the only place where the "any starting point" clause of A contraction of a nonempty complete metric space into itself has exactly one fixed point, the limit of the iterates from any starting point is used for something other than reassurance.
Which bound to use. The a priori bound answers "how many steps do I need", since $q^{\,n}C < \varepsilon$ can be solved for $n$ before computing anything; the a posteriori bound answers "how good is what I have", and it is usually far smaller, because $d(x_{n+1},x_n)$ is itself already of size $q^{\,n}$ . A worked instance of both, for $\sqrt{2}$ , is The map $x \mapsto (x + 2/x)/2$ is a contraction of $[1,2]$ with fixed point $\sqrt{2}$ , and the a priori bound gives the error after $n$ steps ↗.
Both bounds degrade as $q \to 1$ , through the factor $1/(1-q)$ , and neither says anything at $q = 1$ , where the theorem itself is false (FALSE: $d(fx, fy) < d(x,y)$ for all $x \ne y$ on a complete metric space forces a fixed point).

Depends on

Used by

The map x ↦ (x + 2/x)/2 is a contraction of [1,2] with fixed point √2, and the a priori bound gives the error after n steps Example

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 122 results over 31 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.

Sources

Banach fixed-point theorem (Wikipedia) (standard reference, not scraped)
Fixed-point iteration (Wikipedia) (standard reference, not scraped)

The a priori bound d(x∗,xn)≤qnd(x1,x0)/(1−q)d(x^{*}, x_n) \le q^n d(x_1,x_0)/(1-q)d(x∗,xn​)≤qnd(x1​,x0​)/(1−q) and the a posteriori bound d(x∗,xn+1)≤q d(xn+1,xn)/(1−q)d(x^{*}, x_{n+1}) \le q\,d(x_{n+1},x_n)/(1-q)d(x∗,xn+1​)≤qd(xn+1​,xn​)/(1−q)