Convergence of Linear Recurrences

From a recurrence to an explicit formula

A recurrence defines each term from an earlier term. For example, once an initial value is given, the rule \(x_{n+1}=\frac12x_n+3\) determines the whole sequence. Computing several terms can reveal a pattern, but an explicit formula is more useful: it describes the \(n\)th term directly and makes the limit question precise.

This tutorial considers first-order linear recurrences with constant coefficients. “First-order” means that \(x_{n+1}\) depends only on the preceding term \(x_n\), and “linear” means the dependence has the form of a constant multiple of \(x_n\), plus a constant.

The number \(a\) determines how a difference between a term and a fixed point changes at each step. The number \(b\) shifts the recurrence. When \(a\ne 1\), the recurrence has a fixed point: a value \(L\) that stays unchanged under the rule, so \(L=aL+b\). Solving gives \(L=\frac{b}{1-a}\). This value is useful, but it is not automatically the limit; the multiplier \(a\) and the initial value matter too.

The explicit formula and why it works

When \(a\ne 1\), subtract the fixed point \(L\) from each term. The recurrence then becomes a simple multiplication rule for the difference. Repeating that rule gives the explicit formula.

Here is a direct verification of the formula for \(a\ne 1\). Set \(L=\frac{b}{1-a}\), so \(aL+b=L\). If \(x_n=L+a^n(x_0-L)\), then

At \(n=0\), the formula gives \(x_0=L+(x_0-L)=x_0\), so it also has the required initial value. Thus it both starts at the specified term and follows the recurrence. For \(a=1\), the formula \(x_n=x_0+nb\) gives \(x_0\) at \(n=0\); adding \(b\) increases it to \(x_0+(n+1)b\), as required.

Using the formula to determine convergence

For \(a\ne 1\), the formula separates the fixed point \(L\) from the term \(a^n(x_0-L)\). The earlier result on exponential decay gives \(a^n\to 0\) when \(|a|<1\). In that case the second part vanishes, and the sequence converges to \(L\). If \(|a|\ge 1\), the behavior depends on whether the coefficient \(x_0-L\) is zero and on the special cases \(a=1\) and \(a=-1\).

For \(a=-1\), the fixed point is \(L=\frac{b}{2}\), and the explicit formula is \(x_n=L+(-1)^n(x_0-L)\). If \(x_0\ne L\), the even-indexed terms equal \(L+(x_0-L)\), while the odd-indexed terms equal \(L-(x_0-L)\). These are distinct, so the sequence does not converge. If \(x_0=L\), every term equals \(L\).

For \(|a|>1\), the formula gives \(x_n=L+a^n(x_0-L)\). If \(x_0\ne L\), the magnitude of the second term grows without bound because \(|a|^n\) grows without bound. Adding the fixed number \(L\) cannot make the sequence converge. If \(x_0=L\), the second term is always zero, so the sequence is constant.

When \(a=1\), the formula is \(x_n=x_0+nb\). If \(b=0\), every term equals \(x_0\). If \(b\ne0\), the terms move by the same nonzero amount at every step and are unbounded, so they do not converge.

Worked examples

A common mistake: treating every fixed point as a limit

A common error is to solve \(L=aL+b\), find a fixed point, and conclude that the sequence converges to it. The fixed-point equation only identifies a value that remains unchanged under the recurrence; it does not establish that the sequence approaches that value.

For instance, with \(x_{n+1}=-2x_n+3\) and \(x_0=0\), the fixed point is \(L=\frac{3}{1-(-2)}=1\). The incorrect conclusion is “the limit is \(1\), because \(1\) is the fixed point.” But the explicit formula is

The term \((-2)^n\) does not tend to zero; its magnitude grows. The sequence therefore does not converge. The correction is to use the explicit formula and check the multiplier, rather than assume that a fixed point is necessarily a limit.

Another special-case error is dividing by \(1-a\) when \(a=1\). That denominator is zero, so the fixed-point formula does not apply. Instead, use \(x_n=x_0+nb\) and determine convergence from whether \(b=0\).

Why the explicit formula is useful

The recurrence form describes how to move from one term to the next; the explicit form exposes the long-term behavior. In particular, it shows that when \(|a|<1\), the initial difference \(x_0-L\) is repeatedly multiplied by a factor whose magnitude is less than one. This shrinking difference explains why different starting values all approach the same fixed point. When the multiplier has magnitude greater than one, deviations instead grow unless the starting value is already the fixed point.

For a recurrence of this form, a reliable procedure is to identify \(a\), \(b\), and \(x_0\); separate the case \(a=1\); find the fixed point when \(a\ne1\); derive the explicit formula; and then use the size and sign of \(a\) to classify convergence. Substituting the formula into the initial condition and recurrence is a useful final check.