Constructing the Iterative Sequence

Starting an Iteration

The Contraction Mapping Theorem concerns a sequence formed by repeatedly applying a map. In this tutorial, the task is to construct that sequence precisely: choose a starting point, apply the map, and use each new output as the next input. This construction is the same whether or not the sequence is known to converge.

For a contraction $f:X\to X$, the hypotheses in the Contraction Mapping Theorem include a complete metric space and a contraction constant $q<1$. These conditions are important for the theorem’s conclusions, but they are not needed just to define the successive terms. To construct the sequence, it is enough that $f$ be a self-map: its output always belongs to the set on which it can be applied again.

Definition: Let $f:X\to X$ be a map, and choose $x_0\in X$. The iterative sequence, or orbit of $x_0$ under $f$, is the sequence $(x_n)_{n\geq 0}$ defined recursively by $$ x_{n+1}=f(x_n)\qquad(n\geq 0). $$ The point $x_0$ is the starting point, and $x_{n+1}$ is obtained by applying $f$ to $x_n$.

The indexing convention matters. The initial value is $x_0$, so the first application of $f$ gives $x_1=f(x_0)$, the second gives $x_2=f(x_1)=f(f(x_0))$, and in general $x_n$ is obtained after $n$ applications. A sequence defined instead by $x_{n+1}=f(x_n)$ but with its initial value labelled $x_1$ is possible, but it uses a different indexing convention. Keeping the initial point and the first output distinct prevents off-by-one errors in formulas and estimates.

Why the Recursion Is Well-Defined

A recursive rule is useful only if it supplies every term and does not leave room for two different sequences with the same starting point. For a self-map, both properties follow directly from the rule and induction. Completeness and the contraction inequality are not involved.

Theorem (Existence and Uniqueness of the Iterative Sequence): Let $f:X\to X$, and let $x_0\in X$. There is exactly one sequence $(x_n)_{n\geq 0}$ in $X$ such that $x_0$ is its initial term and $x_{n+1}=f(x_n)$ for every $n\geq 0$.

Proof. The initial term $x_0$ belongs to $X$ by choice. If $x_n\in X$, then $f(x_n)\in X$, because $f$ maps $X$ into itself. Define $x_{n+1}=f(x_n)$. Induction therefore constructs a term in $X$ at every nonnegative integer index.

For uniqueness, suppose $(y_n)_{n\geq 0}$ is another sequence in $X$ with $y_0=x_0$ and $y_{n+1}=f(y_n)$. We prove $y_n=x_n$ for all $n$. This holds at $n=0$. If $y_n=x_n$, then

y_{n+1}=f(y_n)=f(x_n)=x_{n+1}.

Induction gives equality at every index. Thus the recursive rule determines exactly one sequence. $\square$

For a contraction, this theorem licenses the notation $x_0,x_1,x_2,\ldots$ without needing to make a new choice at each stage. The self-map condition is essential to the construction: if $f(x_n)$ lies outside $X$, then the next application of $f$ may not be defined. By contrast, completeness is a condition used later to establish convergence, not a prerequisite for forming the orbit.

Finite Iterates and the Tail of an Orbit

It is sometimes convenient to describe an orbit by powers of the map. Define $f^0$ to be the identity map on $X$, and, for $n\geq 0$, define $f^{n+1}=f\circ f^n$. With this convention, $f^n$ means $n$ repeated applications of $f$, not a numerical power. The recursive sequence can then be written $x_n=f^n(x_0)$.

Theorem (Orbit and Tail Identity): Let $f:X\to X$, let $x_0\in X$, and define $x_{n+1}=f(x_n)$. For every pair of nonnegative integers $k,n$, $$ x_{k+n}=f^n(x_k). $$ In particular, the terms $x_k,x_{k+1},x_{k+2},\ldots$ are precisely the iterative sequence obtained by starting at $x_k$.

Proof. Fix $k$. When $n=0$, the identity reads $x_k=f^0(x_k)$, which holds because $f^0$ is the identity. Suppose it holds for some $n$. Then

x_{k+n+1} =f(x_{k+n}) =f\bigl(f^n(x_k)\bigr) =f^{n+1}(x_k).

The first equality is the recursive rule, and the last follows from the definition of $f^{n+1}$. Induction proves the identity for every $n$, for each fixed $k$. The sequence starting at $x_k$ has $n$-th term $f^n(x_k)$, so the identity identifies it with the original sequence from index $k$ onward. $\square$

This tail identity is useful when an argument begins at a later term rather than at the original starting point. For example, an estimate that holds for every starting point can be applied to the tail by taking $x_k$ as the new initial point. The identity also clarifies that each tail follows exactly the same iteration rule; it is not a separate construction with a different map.

Worked Examples: Building the Terms

Worked Example: An Affine Map on an Interval

Let $X=[0,1]$, choose $x_0=1$, and define $f(x)=(1+x)/4$. For every $x\in[0,1]$, $1/4\leq f(x)\leq 1/2$, so $f$ maps $X$ into itself and the recursion can be continued indefinitely. Its first terms are

x_1=f(1)=\frac12,\qquad x_2=f\left(\frac12\right)=\frac38,\qquad x_3=f\left(\frac38\right)=\frac{11}{32}.

For example, $f(3/8)=(1+3/8)/4=(11/8)/4=11/32$, so the third value follows from applying the map to $x_2$, not to $x_0$ again. The map is a contraction because, for $x,y\in[0,1]$,

|f(x)-f(y)| =\frac14|x-y|.

The construction itself required only the self-map property. The contraction estimate is additional information that can be used when studying what happens to the sequence. This example also illustrates the tail identity: starting from $x_1=1/2$ gives the sequence $1/2,3/8,11/32,\ldots$, which is exactly the original sequence with its first term removed.

Worked Example: A Constant Map

Let $X=\mathbb{R}$, let $c\in\mathbb{R}$, and define $f(x)=c$ for every $x\in\mathbb{R}$. Starting at any $x_0$, the recursion gives

x_1=c,\qquad x_2=f(c)=c,\qquad x_3=f(c)=c.

Every term from $x_1$ onward equals $c$. For any $x,y\in\mathbb{R}$, $|f(x)-f(y)|=|c-c|=0$, so this map is a contraction with constant $q=0$. If the initial point already equals $c$, then $x_0=c$ as well and the entire sequence is constant. If it does not, the initial point is the one term that may differ from the rest. The distinction is important: “the sequence is eventually constant” does not mean that its initial term must equal all later terms.

Worked Example: A Nonlinear Map on an Interval

Let $X=[0,1]$, set $x_0=0$, and define $f(x)=1/(2+x)$. Since $2\leq 2+x\leq 3$ on $X$, we have $1/3\leq f(x)\leq 1/2$; hence $f$ maps the interval into itself. The first terms are

x_1=\frac12,\qquad x_2=\frac{1}{2+1/2}=\frac25,\qquad x_3=\frac{1}{2+2/5}=\frac{5}{12}.

The map is a contraction: for $x,y\in[0,1]$,

|f(x)-f(y)| =\left|\frac{1}{2+x}-\frac{1}{2+y}\right| =\frac{|x-y|}{(2+x)(2+y)} \leq \frac14|x-y|,

because both denominator factors are at least $2$. Each term is obtained by substituting the immediately preceding term into the same formula. In particular, $x_3$ is $1/(2+2/5)=5/12$, not $1/(2+x_0)$. This is a simple place to check an implementation of the recursion: the input at step $n$ must be the value just computed at step $n-1$.

Repeated Terms in a Contraction Orbit

A contraction orbit cannot return to an earlier term and then continue around a nonconstant cycle. This fact gives a useful check on calculations: if two terms in a purported contraction orbit coincide, all later terms must in fact be the same fixed point. The proof uses the Contraction Estimate for Iterates established earlier in Contractions.

Theorem (A Repeated Term Forces a Fixed Point): Let $f:X\to X$ be a contraction with constant $q$, where $0\leq q<1$, and let $x_{n+1}=f(x_n)$. If $x_m=x_n$ for some integers $m<n$, then $x_m=x_{m+1}$. Consequently, $x_m$ is a fixed point and $x_j=x_m$ for every $j\geq m$.

Proof. Put $r=n-m$, so $r\geq1$ and $x_{m+r}=x_m$. The Orbit and Tail Identity gives $f^r(x_m)=x_{m+r}=x_m$. Applying the same $r$ iterates to $x_{m+1}$ gives

f^r(x_{m+1})=x_{m+r+1}=f(x_{m+r})=f(x_m)=x_{m+1}.

Thus $f^r$ maps each of $x_m$ and $x_{m+1}$ to itself. By the Contraction Estimate for Iterates,

d(x_m,x_{m+1}) =d\bigl(f^r(x_m),f^r(x_{m+1})\bigr) \leq q^r d(x_m,x_{m+1}).

Since $0\leq q<1$ and $r\geq1$, $q^r<1$. The displayed inequality implies $(1-q^r)d(x_m,x_{m+1})\leq0$. The distance is nonnegative and $1-q^r>0$, so $d(x_m,x_{m+1})=0$. Therefore $x_m=x_{m+1}=f(x_m)$, making $x_m$ a fixed point. Applying the recursion repeatedly now gives $x_j=x_m$ for every $j\geq m$. $\square$

What Construction Does—and Does Not—Establish

Constructing the iterative sequence gives a well-defined list of points in $X$, and the Orbit and Tail Identity describes how that list behaves when restarted from a later term. Neither fact by itself proves that the terms approach one another or converge. Those are separate questions. In the contraction setting, the Cauchy Estimate for Successive Iterates supplies control of the distances between terms, while completeness is used in the Contraction Mapping Theorem to ensure that a Cauchy sequence has a limit in $X$.

When writing down an iteration, check the following details before using any convergence result:

Specify the starting point $x_0$ and the index at which it occurs.
Check that $f$ maps the chosen domain into itself, so every next term can be formed.
At each step, substitute the preceding term into $f$, rather than repeatedly substituting the original starting point.
Keep the construction separate from later claims about Cauchy behavior or convergence.

For a contraction with $q=0$, the contraction inequality forces $f$ to be constant: for all $x,y\in X$, $d(f(x),f(y))\leq0$, so $f(x)=f(y)$. Its orbit is therefore constant from $x_1$ onward, as in the constant-map example. For $0<q<1$, the recursion need not become exactly constant after finitely many steps; the terms can keep changing even when their distances become small. This distinction is one reason to compute the sequence carefully rather than infer its behavior from a few initial values.

Check Your Understanding

Use the definitions and results above to answer the following questions.

Why is the self-map condition $f:X\to X$ enough to construct every term, even when $X$ is not complete?
With the convention $x_0$ as the starting point, what is $x_2$ in terms of $f$ and $x_0$?
For an orbit starting at $x_0$, which starting point generates the tail $x_k,x_{k+1},\ldots$?
If a contraction orbit has $x_m=x_n$ for $m<n$, what does the Repeated Term theorem imply about all terms from index $m$ onward?
For $f(x)=1/(2+x)$ and $x_0=0$, verify the calculation of $x_3$ by substituting $x_2=2/5$ into the recurrence.