Recursive Sequence Convergence

Why Recursive Sequences Need an Argument

A recursive rule specifies each term from an earlier one, but that alone does not guarantee convergence. For example, a rule can make the terms alternate between two values. To prove convergence, we need to control how much the terms can change as the iteration proceeds. A particularly useful situation is when successive differences shrink by a fixed factor less than one.

Throughout this tutorial, a recursive sequence has an initial value $a_0$ and is defined by a rule such as $a_{n+1}=f(a_n)$. The function $f$ may also be required to keep every iterate inside a specified set. The key idea is to estimate successive differences first, then add those estimates to control the distance between any two sufficiently late terms.

Theorem (Geometric Successive-Difference Criterion): Suppose $0<q<1$, $C\geq0$, and a real sequence $(a_n)$ satisfies $$ |a_{n+1}-a_n|\leq Cq^n \qquad(n\in\mathbb{N}_0). $$ Then $(a_n)$ converges to a finite limit $L$, and $$ |a_n-L|\leq \frac{Cq^n}{1-q} \qquad(n\in\mathbb{N}_0). $$

Proof. Let $m>n$. Repeated use of the triangle inequality gives

|a_m-a_n| \leq \sum_{k=n}^{m-1}|a_{k+1}-a_k| \leq C\sum_{k=n}^{m-1}q^k \leq \frac{Cq^n}{1-q}.

The last bound tends to zero as $n\to\infty$, independently of $m>n$. Given $\varepsilon>0$, choose $N$ so that $Cq^N/(1-q)<\varepsilon$ (if $C=0$, every term is equal and the conclusion is immediate). For $m>n\geq N$, the displayed estimate then gives $|a_m-a_n|<\varepsilon$. The sequence is Cauchy, so the Cauchy Criterion for Real Sequences implies that it converges to some finite $L$.

For fixed $n$, the same estimate holds for every $m>n$. Letting $m\to\infty$ and using $a_m\to L$ gives

|a_n-L|\leq \frac{Cq^n}{1-q}.

This proves both convergence and the stated error bound. $\square$

The denominator $1-q$ comes from adding the entire geometric tail $q^n+q^{n+1}+\cdots$. The estimate is useful even when the limit is not known explicitly: it bounds how far an iterate can be from that limit. A bound on just one successive difference would not suffice; what matters here is a bound on every successive difference with a shrinking geometric factor.

Recursive Rules That Contract Distances

A common way to obtain geometric successive-difference bounds is to require that the recursive rule shrink distances. The set on which the rule acts must also contain the iterates; otherwise, the estimates might only apply for a few steps.

Definition: Let $E\subseteq\mathbb{R}$. A function $f:E\to E$ is a contraction if there is a constant $q$ with $0\leq q<1$ such that $$ |f(x)-f(y)|\leq q|x-y| \qquad\text{for all }x,y\in E. $$ A point $p\in E$ is a fixed point of $f$ if $f(p)=p$.

The condition $f:E\to E$ says that applying the rule to a point in $E$ produces another point in $E$, so iteration stays in the set. The contraction inequality says that the distance between any two images is at most a fixed fraction of the distance between the original points. When $q=0$, all images are identical; when $0<q<1$, distances decrease at every step.

Theorem (Convergence of a Contraction Iteration): Let $E$ be a nonempty closed subset of $\mathbb{R}$, and let $f:E\to E$ be a contraction with constant $q$, where $0\leq q<1$. For any $a_0\in E$, define $a_{n+1}=f(a_n)$. Then $(a_n)$ converges to a point $p\in E$, and $p$ is the unique fixed point of $f$ in $E$.

Proof. First suppose $0<q<1$. Since $f$ maps $E$ into itself, induction gives $a_n\in E$ for every $n$. Applying the contraction inequality to $a_{n+1}=f(a_n)$ and $a_n=f(a_{n-1})$, for $n\geq1$, yields

|a_{n+1}-a_n|\leq q|a_n-a_{n-1}|.

Applying this estimate repeatedly, with the initial difference $|a_1-a_0|$, gives

|a_{n+1}-a_n|\leq q^n|a_1-a_0| \qquad(n\in\mathbb{N}_0).

For $n=0$ this is equality; each later case follows by multiplying the preceding bound by $q$. The Geometric Successive-Difference Criterion, with $C=|a_1-a_0|$, now gives convergence to some $p\in\mathbb{R}$. Since every $a_n\in E$ and $E$ is closed, the Sequential Characterization of Closed Sets implies $p\in E$.

We next show that $p$ is a fixed point. The contraction inequality gives

|f(a_n)-f(p)|\leq q|a_n-p|\longrightarrow 0.

Thus $f(a_n)\to f(p)$. But $f(a_n)=a_{n+1}$, and the shifted sequence $(a_{n+1})$ also converges to $p$. Uniqueness of limits therefore gives $f(p)=p$.

To prove uniqueness, suppose $u,v\in E$ are both fixed points. Then

|u-v|=|f(u)-f(v)|\leq q|u-v|.

Because $q<1$, this inequality is possible only if $|u-v|=0$, so $u=v$.

If $q=0$, the contraction inequality says $|f(x)-f(y)|=0$ for every $x,y\in E$. Thus $f$ is constant on $E$, with some value $c\in E$. We have $a_1=c$, and $f(c)=c$, so every term from $a_1$ onward equals $c$. The sequence converges to $c$, which is a fixed point. Any fixed point must equal the constant value $c$, so it is unique. This covers all allowed values of $q$. $\square$

Closedness matters because the Cauchy argument gives a real limit, but it does not by itself guarantee that the limit belongs to $E$. The theorem uses closedness precisely to keep the limit in the domain where the recursive rule and its fixed-point equation are defined.

Worked Examples

Worked Example: An Affine Recursion with an Exact Error

Let $a_0=0$ and define

a_{n+1}=\frac{a_n+4}{3}.

The associated function is $f(x)=(x+4)/3$, which maps $\mathbb{R}$ into $\mathbb{R}$. For any real $x,y$,

|f(x)-f(y)| =\left|\frac{x-y}{3}\right| =\frac13|x-y|.

It is a contraction with $q=1/3$. The fixed point solves $p=(p+4)/3$, so $3p=p+4$ and $p=2$. The contraction theorem proves convergence to this unique fixed point.

Here the error can also be calculated exactly. Substituting the recurrence gives

a_{n+1}-2=\frac{a_n+4}{3}-2=\frac{a_n-2}{3}.

Since $a_0-2=-2$, induction yields $a_n-2=-2(1/3)^n$, and hence $|a_n-2|=2(1/3)^n$. The general contraction estimate uses $|a_1-a_0|=4/3$, so it gives

|a_n-2| \leq \frac{(1/3)^n}{1-1/3}|a_1-a_0| =\frac{(1/3)^n}{2/3}\cdot\frac43 =2(1/3)^n.

This equals the exact error, so the estimate is sharp in this example. In particular, $a_1=4/3$, and the first error is $2/3$, consistent with $2(1/3)^1=2/3$.

Worked Example: A Nonlinear Recursion on a Closed Interval

Define $f:[0,1]\to[0,1]$ by $f(x)=(1+x^2)/4$, and choose any $a_0\in[0,1]$. If $0\leq x\leq1$, then $1/4\leq f(x)\leq1/2$, so $f$ maps the interval into itself. For $x,y\in[0,1]$,

|f(x)-f(y)| =\frac{|x-y||x+y|}{4} \leq \frac12|x-y|,

because $x+y\leq2$. Thus $f$ is a contraction with $q=1/2$. The interval $[0,1]$ is closed, so the contraction theorem ensures that the iterates converge to its unique fixed point.

To identify that point, solve $p=(1+p^2)/4$, which is equivalent to $p^2-4p+1=0$. The quadratic formula gives $p=2\pm\sqrt{3}$. Since $1<\sqrt{3}<2$, the value $2-\sqrt{3}$ lies in $[0,1]$, while $2+\sqrt{3}>1$. Therefore the unique fixed point in the interval is $2-\sqrt{3}$, and every starting value in $[0,1]$ produces iterates converging to it.

For example, if $a_0=0$, then $a_1=1/4$ and $a_2=(1+1/16)/4=17/64$. The contraction estimate also gives a quantitative error bound. Since $|a_1-a_0|=1/4$,

|a_n-(2-\sqrt{3})| \leq \frac{(1/2)^n}{1-1/2}\cdot\frac14 =\frac{1}{2^{n+1}}.

The estimate does not require evaluating the later iterates explicitly.

Worked Example: A Recursive Rule That Does Not Converge

Let $f(x)=1-x$ on $[0,1]$, and start with $a_0=0$. The rule maps $[0,1]$ into itself, but

$$ |f(x)-f(y)|=|x-y|. $$

It does not give a contraction with any $q<1$. The iterates are $a_0=0$, $a_1=1$, $a_2=0$, $a_3=1$, and so on. The even-indexed subsequence is constantly $0$, and the odd-indexed subsequence is constantly $1$. Since these subsequences have distinct limits, the theorem on distinct subsequence limits obstructing convergence shows that $(a_n)$ does not converge.

The rule does have a fixed point, since $x=1-x$ gives $x=1/2$. But starting at $0$ does not lead to that fixed point. This example shows why the existence of a fixed point, or even the fact that the rule maps an interval into itself, is not enough to ensure convergence of every iteration.

What the Contraction Condition Does—and Does Not—Say

The contraction theorem combines three separate ingredients. The map sends iterates back into the set; strict distance reduction makes successive differences decay geometrically; and closedness ensures that the resulting limit remains in the set. Together these give convergence from every permitted starting point and identify the limit as the unique fixed point.

The theorem is a sufficient condition, not a necessary one. Some recursive sequences converge even when their defining rule is not a contraction on the chosen set. Conversely, a recursive formula by itself supplies no convergence guarantee. A common mistake is to find a fixed point by solving $f(p)=p$ and then assume that the iterates converge to it. The alternating example shows that solving the fixed-point equation does not establish that conclusion. The distance estimate—or another valid convergence argument—is essential.

When a contraction estimate is available, the successive-difference criterion is often the most direct route: compare consecutive iterates, obtain a geometric bound, and sum the bounds to control an entire tail. The Cauchy Criterion for Real Sequences then supplies a finite limit, while continuity as encoded in the contraction inequality lets the recursive equation pass to that limit.

Check Your Understanding

Use the definitions and results in this tutorial to answer the following questions.

Why does a geometric bound on $|a_{n+1}-a_n|$ imply that the sequence is Cauchy?
In the contraction iteration theorem, what role does the assumption that $E$ is closed play?
For a contraction with constant $q$, how can the first difference $|a_1-a_0|$ be used to bound later successive differences?
Why does the contraction inequality guarantee that two fixed points in $E$ must be equal?
Why does the rule $f(x)=1-x$ on $[0,1]$, started at $0$, fail to converge even though it has a fixed point?

What You'll Learn