Convergence Of Affine Recurrences

Introduction

An affine recurrence updates a term by multiplying the current value by a fixed number and adding a constant. When the multiplier lies strictly between zero and one, each update draws the term toward a particular value: the recurrence’s fixed point.

Where the initial value lies relative to that fixed point determines the sequence’s direction. Starting below it gives an increasing sequence; starting above it gives a decreasing sequence. In either case, the terms stay on their original side, and the sequence converges to the fixed point.

Definition and Fixed Point

Solving the fixed-point equation gives a unique value, since \(1-r>0\):

The fixed point is the value that would remain unchanged if used as the current term: \(rL+c=L\). It is the natural candidate for the limit, but identifying a candidate does not by itself prove convergence. We will show that the terms move monotonically, remain bounded, and therefore converge.

Compare Each Term with the Fixed Point

Subtract \(L\) from both sides of the recurrence. Because \(rL+c=L\), the difference between the next term and the fixed point is a scaled version of the current difference:

Since \(r>0\), multiplying by \(r\) preserves the sign. Thus, if a term is below \(L\), the next term is also below \(L\); if a term is above \(L\), the next term is also above \(L\). More precisely, the distance from the fixed point is multiplied by \(r\), so it becomes smaller unless it is already zero.

The direction of motion follows from the consecutive difference:

Here \(1-r>0\). Therefore the sign of \(x_{n+1}-x_n\) is the sign of \(L-x_n\): terms below \(L\) increase, and terms above \(L\) decrease.

Exact Formula and Its Derivation

The comparison with the fixed point also gives an exact expression for every term. Repeatedly applying \(x_{n+1}-L=r(x_n-L)\) yields the formula below. The induction verifies it for all \(n\geq 1\).

This formula explains both the direction and the convergence. Because \(r^{n-1}>0\), the difference \(x_n-L\) has the same sign as \(x_1-L\). Also, \(r^{n-1}\) tends to zero when \(0<r<1\). To see the decay, write \(1/r=1+h\) for \(h>0\). The binomial inequality gives \((1+h)^m\geq 1+mh\) for positive integers \(m\), so \(0<r^m\leq 1/(1+mh)\), which tends to zero. The exact formula therefore gives \(x_n\to L\).

Monotonicity, Bounds, and Convergence

The formula gives a direct route to the limit. The monotone convergence theorem gives another: once a real sequence is shown to be monotone and bounded, it converges. In this recurrence, the fixed point supplies the bound, while the consecutive difference supplies monotonicity.

To verify the increasing case, suppose \(x_1<L\). The error relation gives \(x_n-L=r^{n-1}(x_1-L)<0\), so \(x_n<L\) at every index. Then \(x_{n+1}-x_n=(1-r)(L-x_n)>0\), so the sequence is strictly increasing and bounded above by \(L\). By the monotone convergence theorem it has a limit. The exact formula, together with \(r^{n-1}\to 0\), identifies that limit as \(L\).

For \(x_1>L\), the error relation instead gives \(x_n>L\) at every index. Thus \(x_{n+1}-x_n=(1-r)(L-x_n)<0\): the sequence is strictly decreasing and bounded below by \(L\). It converges by the monotone convergence theorem, and the exact formula again identifies the limit as \(L\). If \(x_1=L\), then \(x_2=rL+c=L\); the recurrence keeps every subsequent term at \(L\).

Worked Examples

A Common Sign Error

A frequent mistake is to see that \(r-1<0\) and conclude that the consecutive difference must be negative. But the difference is \((r-1)(x_n-L)\); its sign depends on both factors. When \(x_n<L\), both factors are negative, so their product is positive.

For example, in the first worked example, \(r=\frac12\), \(L=6\), and \(x_1=0\). The correct calculation is

Thus \(x_2>x_1\), not \(x_2<x_1\). Keep the full product when determining the sign, or use the equivalent expression \((1-r)(L-x_n)\), whose sign is immediately positive when \(x_n<L\).

Why the Fixed Point Matters

The fixed point gives a reference value that turns a two-parameter recurrence into a simple error update: \(x_{n+1}-L=r(x_n-L)\). This relationship tells us how far a term is from the target and whether it lies above or below it. It is useful both for proving convergence and for estimating how quickly the terms approach their limit: after \(n-1\) updates, the initial error has been multiplied by \(r^{n-1}\).

The fixed-point equation alone does not establish convergence. It identifies a value that would be unchanged by the recurrence; a separate argument is still needed to show that the sequence approaches it. Here, the error formula and the monotone-and-bounded argument supply that justification.