Fixed Points of Recursive Sequences

Fixed Points as Equilibria of a Recursion

For a recursive sequence \(a_{n+1}=f(a_n)\), a fixed point of \(f\) is a value that the rule leaves unchanged. If an iteration starts at that value, every term remains there. But an arbitrary starting value need not produce a sequence that converges to a fixed point: convergence depends on how the rule moves nearby points, not just on the solutions of an equation.

The last statement follows by induction: \(a_0=p\), and if \(a_n=p\), then \(a_{n+1}=f(p)=p\). A fixed point is therefore an equilibrium for the recursive rule. It is not automatically the limit of an iteration started elsewhere.

Earlier in this course, the theorem A Continuous Recursive Limit Is a Fixed Point established a useful necessary condition: if \(a_n\to L\) and \(f\) is continuous at \(L\), then \(f(L)=L\). This tutorial develops two further ideas. Endpoint inequalities can ensure that a continuous function has a fixed point, and a monotone iteration can select a particular fixed point relative to its starting value.

Endpoint Inequalities Guarantee a Fixed Point

To find a fixed point, rewrite \(f(x)=x\) as \(f(x)-x=0\). If the continuous function \(f(x)-x\) is nonnegative at one endpoint of an interval and nonpositive at the other, the Intermediate Value Theorem guarantees a zero between them. This argument establishes existence, but not uniqueness.

Proof. Define \(g(x)=f(x)-x\) for \(x\in[A,B]\). Since \(f\) and the identity function are continuous, \(g\) is continuous. The endpoint conditions give

If \(A<B\), the Intermediate Value Theorem gives a point \(p\in[A,B]\) with \(g(p)=0\). Thus \(f(p)-p=0\), so \(f(p)=p\). If \(A=B\), the two endpoint conditions give \(f(A)\geq A\) and \(f(A)\leq A\), hence \(f(A)=A\), which is already a fixed point. In either case, a fixed point belongs to \([A,B]\). \(\square\)

Monotone Iteration Selects a Fixed Point

A fixed point can also help control the terms of a recursive sequence. Suppose \(f\) is nondecreasing, meaning that \(x\leq y\) implies \(f(x)\leq f(y)\). If \(p\) is a fixed point and the initial value satisfies \(a_0\leq p\), then the iterates cannot pass above \(p\): whenever \(a_n\leq p\), order preservation gives \(a_{n+1}=f(a_n)\leq f(p)=p\). A corresponding statement holds below a fixed point when \(a_0\geq p\).

Proof. First suppose \(a_1\geq a_0\). We show that the iteration is nondecreasing. The first inequality holds by assumption. If \(a_n\geq a_{n-1}\), then the fact that \(f\) is nondecreasing gives

Induction proves \(a_{n+1}\geq a_n\) for every \(n\). Since every term lies in \(J\), the sequence is bounded above by \(B\). The Monotone Convergence Theorem therefore gives a finite limit \(L\in[a_0,B]\). By the theorem A Continuous Recursive Limit Is a Fixed Point, \(f(L)=L\).

Now let \(p\in[a_0,B]\) be any fixed point of \(f\). We prove \(a_n\leq p\) for every \(n\). The initial inequality \(a_0\leq p\) holds. If \(a_n\leq p\), then, because \(f\) is nondecreasing,

Thus induction gives \(a_n\leq p\) for all \(n\). Taking the limit yields \(L\leq p\). Since \(L\) is itself a fixed point in \([a_0,B]\) and is no greater than any fixed point there, it is the least such fixed point.

For the other case, suppose \(a_1\leq a_0\). If \(a_n\leq a_{n-1}\), then order preservation gives \(a_{n+1}=f(a_n)\leq f(a_{n-1})=a_n\). Hence the sequence is nonincreasing. It is bounded below by \(A\), so the Monotone Convergence Theorem gives a limit \(L\in[A,a_0]\), and continuity again implies \(f(L)=L\). If \(p\in[A,a_0]\) is any fixed point, then \(a_0\geq p\); induction using \(a_n\geq p\) gives \(a_{n+1}=f(a_n)\geq f(p)=p\). Thus \(a_n\geq p\) for every \(n\), and \(L\geq p\). Therefore \(L\) is the greatest fixed point in \([A,a_0]\). \(\square\)

The theorem describes more than the existence of a limit. It identifies which fixed point the iteration reaches when there may be several. The initial direction determines whether the limit is the least fixed point above the starting value or the greatest fixed point below it. The hypotheses matter: the interval keeps the iterates bounded, monotonicity of \(f\) preserves comparisons, and continuity allows the limit to satisfy the fixed-point equation.

A Fixed Point Does Not Ensure Convergence

A fixed-point equation describes where a single application of the rule leaves a value unchanged. It does not, by itself, tell us what repeated applications do to other values. The next example has a fixed point but also has an iteration that does not converge.

This example also shows why the hypotheses in the selection theorem cannot be dropped casually: \(f(x)=1-x\) is decreasing, not nondecreasing, and the iteration is not monotone. A fixed point can be found by solving an equation, but predicting an iteration requires additional information about the rule and the starting value. In particular, do not infer convergence merely from continuity or from the existence of a fixed point.

A useful order of analysis is to identify candidate fixed points, check whether the rule preserves an interval, and examine the direction of the first step. If the rule is nondecreasing and the iteration begins by moving upward or downward, the fixed-point selection theorem can locate its limit among all fixed points on the relevant side of the starting value. If the iteration is already known to converge and the rule is continuous at the limit, the continuous recursive limit theorem then supplies the fixed-point equation.