Fixed-Point Equations That Do Not Prove Convergence

Why a Fixed-Point Equation Is Not a Convergence Proof

A common first step in studying a recursive sequence is to suppose it converges to a limit \(L\). If the recurrence is \(x_{n+1}=f(x_n)\), this supposition often leads to the equation \(L=f(L)\). Solving that equation can be useful: it identifies values that a limit might have. But it does not show that the sequence actually converges.

The distinction matters because a recurrence can have fixed points while its iterates oscillate, move away from those points, or approach a different one depending on the initial value. To determine what the sequence does, we need an argument about the sequence itself, such as proving it is monotone and bounded.

Definition: A fixed point of a function \(f\) is a value \(L\) in its domain such that \(f(L)=L\). A fixed point is a property of the function. A limit is a property of a particular sequence generated from a specified initial value.

These notions are related, but they are not interchangeable. For a recurrence \(x_{n+1}=f(x_n)\), the initial value \(x_0\) and the rule \(f\) determine the sequence. A solution of \(L=f(L)\) does not by itself tell us whether that sequence converges to \(L\), converges at all, or remains near \(L\).

When a Limit Must Be a Fixed Point

There is a precise implication that explains why fixed-point equations are useful. If a recursively defined sequence converges and the recurrence map is continuous at its limit, then the limit must be a fixed point. Continuity is essential to this conclusion.

Theorem: Suppose \(x_{n+1}=f(x_n)\) for every \(n\), \(x_n\to L\), and \(f\) is continuous at \(L\). Then \(f(L)=L\).

Here, continuity at \(L\) means that whenever inputs approach \(L\), their images under \(f\) approach \(f(L)\). The proof uses both the recurrence and the fact that shifting a convergent sequence by one index does not change its limit.

Take the limit of the left side.
Since \(x_n\to L\), the shifted sequence \(x_{n+1}\) also tends to \(L\).

Use the recurrence and continuity.
Because \(x_{n+1}=f(x_n)\), and \(x_n\to L\), continuity at \(L\) gives \(f(x_n)\to f(L)\).

Compare the limits.
The same sequence \(x_{n+1}=f(x_n)\) tends to both \(L\) and \(f(L)\). Limits are unique, so \(L=f(L)\).

This is a necessary-condition argument: if the sequence converges, then its limit must solve the fixed-point equation, provided continuity holds. It does not reverse the implication. Finding a solution of \(L=f(L)\) does not establish that \(x_n\to L\).

Worked Example: A Bounded Sequence That Oscillates

Consider \(x_{n+1}=2-x_n\) with \(x_0=0\). First calculate the terms directly:

x_1=2-0=2,\qquad x_2=2-2=0,\qquad x_3=2-0=2,\qquad x_4=2-2=0.

The sequence alternates between \(0\) and \(2\). It is bounded, but it does not converge: the even-indexed terms are all \(0\), while the odd-indexed terms are all \(2\), so these two subsequences have different limits.

The map \(f(x)=2-x\) is continuous. Its fixed-point equation gives:

L=2-L \quad\Longrightarrow\quad 2L=2 \quad\Longrightarrow\quad L=1.

Indeed, \(f(1)=2-1=1\), so \(1\) is a fixed point. But the sequence from \(x_0=0\) does not converge to \(1\), or to any other value. The equation finds a fixed point of the map; it does not make the alternating sequence converge. As a check, the recurrence continues to give \(x_{2k}=0\) and \(x_{2k+1}=2\) for every nonnegative integer \(k\).

Prove Convergence Before Using the Fixed-Point Equation

A standard way to establish convergence is to prove that the sequence is monotone and bounded. The monotone convergence theorem states that every increasing sequence bounded above converges, and every decreasing sequence bounded below converges. Once convergence has been established, continuity can be used to identify the limit through the fixed-point equation.

The order of reasoning is important. First establish monotonicity and a bound for the actual sequence. Then conclude that it has a limit. Only after that should the recurrence and continuity be used to determine which fixed point is the limit.

Worked Example: Increasing to a Fixed Point

Define \(x_0=0\) and \(x_{n+1}=x_n+\frac{(1-x_n)^2}{2}\). The first terms are:

x_1=0+\frac{(1-0)^2}{2}=\frac12, $$ $$ x_2=\frac12+\frac{(1-\frac12)^2}{2} =\frac12+\frac18 =\frac58, $$ $$ x_3=\frac58+\frac{(1-\frac58)^2}{2} =\frac58+\frac{(\frac38)^2}{2} =\frac58+\frac9{128} =\frac{89}{128}.

To prove convergence, suppose \(0\le x_n<1\). Then \((1-x_n)^2>0\), so

x_{n+1}-x_n=\frac{(1-x_n)^2}{2}>0.

Thus the next term is larger. Also, writing the distance from \(1\) explicitly gives

1-x_{n+1} =1-x_n-\frac{(1-x_n)^2}{2} =(1-x_n)\left(1-\frac{1-x_n}{2}\right).

Since \(0<1-x_n\le1\), the factor in parentheses is between \(\frac12\) and \(1\). Therefore \(1-x_{n+1}>0\), which means \(x_{n+1}<1\). Starting from \(x_0=0\), induction now shows that every term satisfies \(0\le x_n<1\), and the sequence is increasing.

The sequence is increasing and bounded above by \(1\), so it converges to some \(L\) with \(0\le L\le1\). The recurrence map is continuous, so the theorem gives \(L=L+\frac{(1-L)^2}{2}\). Solving yields \((1-L)^2=0\), hence \(L=1\). Substitution checks the result: \(f(1)=1+\frac{(1-1)^2}{2}=1\).

Multiple Fixed Points: The Initial Value Helps Select the Limit

Even when convergence is proved, the fixed-point equation may have more than one solution. A bound inherited from the initial value can then rule out some candidates. The next example shows why solving the equation alone may leave the limit undetermined.

Worked Example: Selecting Between Two Fixed Points

Let \(x_0=\frac12\) and \(x_{n+1}=x_n^2\). The first terms are

x_1=\left(\frac12\right)^2=\frac14,\qquad x_2=\left(\frac14\right)^2=\frac1{16},\qquad x_3=\left(\frac1{16}\right)^2=\frac1{256}.

Whenever \(0<x_n<1\), multiplying \(x_n\) by itself gives \(0<x_n^2<x_n\). Since \(x_0=\frac12\) lies between \(0\) and \(1\), induction shows that every term remains in this interval and that the sequence is decreasing. It is bounded below by \(0\), so it converges to some \(L\) with \(0\le L\le\frac12\).

The map \(f(x)=x^2\) is continuous, and its fixed-point equation is

L=L^2 \quad\Longleftrightarrow\quad L(L-1)=0 \quad\Longleftrightarrow\quad L=0\ \text{or}\ L=1.

The bound \(L\le\frac12\) rules out \(L=1\), leaving \(L=0\). Substitution confirms that \(f(0)=0\). Thus the fixed-point equation supplies two candidates, while the monotonicity and bound identify the limit for this initial value.

Why Continuity Cannot Be Omitted

The fixed-point conclusion also depends on continuity. Without continuity at the limit, a convergent sequence generated by a recurrence need not have a fixed-point limit. This is not a technical detail: it is exactly what allows us to pass from \(f(x_n)\) to \(f(L)\).

Worked Example: A Convergent Sequence Whose Limit Is Not a Fixed Point

Define \(f\) on \([0,\infty)\) by

f(x)= \begin{cases} \dfrac{x}{1+x},&x>0,\\ 1,&x=0. \end{cases}

Starting with \(x_0=1\), the recurrence gives \(x_1=\frac12\), \(x_2=\frac13\), and \(x_3=\frac14\). In fact, induction gives \(x_n=\frac{1}{n+1}\): if \(x_n=\frac{1}{n+1}\), then

x_{n+1} =\frac{\frac{1}{n+1}}{1+\frac{1}{n+1}} =\frac{\frac{1}{n+1}}{\frac{n+2}{n+1}} =\frac{1}{n+2}.

Hence \(x_n\to0\). But \(f(0)=1\), so the limit is not a fixed point. The map is not continuous at \(0\): for positive \(x\) approaching \(0\), \(f(x)=\frac{x}{1+x}\) approaches \(0\), not \(f(0)=1\). The example shows precisely why continuity at the limit is required in the theorem.

A Reliable Order of Reasoning

When studying a recurrence \(x_{n+1}=f(x_n)\), do not treat the fixed-point equation as a shortcut to convergence. It is a tool for identifying possible limits, and its proper use depends on the conclusions already established about the sequence.

Inspect the recurrence and initial value.
Determine which values the sequence can reach and whether the map is continuous where a possible limit could lie.

Establish behavior of the sequence.
Use inequalities, induction, monotonicity, and bounds to prove convergence when possible. Boundedness alone does not suffice, as the alternating example shows.

Use the fixed-point equation conditionally.
Once convergence is known, continuity implies that the limit solves \(L=f(L)\). Solve the equation and use the sequence’s bounds to identify the correct candidate.

Check the conclusion.
Substitute the proposed limit into the recurrence map, and ensure the argument established convergence rather than merely finding a fixed point.

The fixed-point equation matters because it turns a limit problem into an algebraic one after convergence has been proved. But the algebra cannot replace the sequence argument. A fixed point may coexist with oscillation, several fixed points may require further reasoning to distinguish, and a discontinuity can prevent even a convergent sequence’s limit from being fixed.

Key takeaway: Solving \(L=f(L)\) identifies candidate limits. To conclude that a particular recursive sequence approaches one of them, first prove that the sequence converges; when using the fixed-point equation, also verify continuity at the limit.

Check Your Understanding

Answer each question using the distinction between a fixed point and a sequence limit.

For \(x_{n+1}=f(x_n)\), what assumptions let you conclude that a limit \(L\) must satisfy \(f(L)=L\)?
Why does the recurrence \(x_{n+1}=2-x_n\), \(x_0=0\), not converge even though its map has a fixed point?
In the recurrence \(x_{n+1}=x_n^2\), \(x_0=\frac12\), what rules out the fixed-point candidate \(L=1\)?
Why is boundedness alone insufficient to establish convergence?
What fails in the argument \(x_n\to L\Rightarrow f(x_n)\to f(L)\) if \(f\) is not continuous at \(L\)?