Monotone Recursive Sequences

Monotonicity Begins with a One-Step Comparison

A recursive rule determines each new term from the previous one, but the rule does not automatically make the sequence increase or decrease. To establish monotonicity, compare \(a_{n+1}\) with \(a_n\). For a recursion \(a_{n+1}=f(a_n)\), this comparison is governed by the sign of \(f(a_n)-a_n\). The challenge is to ensure that the terms stay in a region where that sign can be controlled.

An interval that contains the starting value and is preserved by the recursive rule is useful for exactly this reason. Once the sequence is known to stay in that interval, an inequality that holds throughout the interval applies at every step. This approach can prove monotonicity even when \(f\) is not an increasing function.

Definition: An interval \(J\subseteq\mathbb{R}\) is invariant under \(f\) if \(f(x)\in J\) for every \(x\in J\). If \(a_0\in J\) and \(a_{n+1}=f(a_n)\), invariance ensures that every iterate \(a_n\) belongs to \(J\).

Theorem (Monotonicity from the Sign of the Increment): Let \(J\) be an interval invariant under \(f\), and let \(a_0\in J\). Define \(a_{n+1}=f(a_n)\). If \(f(x)\geq x\) for every \(x\in J\), then \((a_n)\) is nondecreasing. If \(f(x)\leq x\) for every \(x\in J\), then \((a_n)\) is nonincreasing.

Proof. Invariance and induction give \(a_n\in J\) for every \(n\): this holds for \(n=0\), and if \(a_n\in J\), then \(a_{n+1}=f(a_n)\in J\). In the first case, apply \(f(x)\geq x\) at \(x=a_n\). It gives

a_{n+1}=f(a_n)\geq a_n \qquad(n\in\mathbb{N}_0),

so the sequence is nondecreasing. In the second case, applying \(f(x)\leq x\) at \(a_n\) gives \(a_{n+1}\leq a_n\) for every \(n\), so the sequence is nonincreasing. \(\square\)

The interval condition is part of the argument, not decoration: the inequality for \(f(x)-x\) only helps at terms where it is known to hold. In applications, it is often efficient to check invariance first and then check the sign of the increment on that interval.

Monotone Functions and Monotone Sequences

A function \(f\) is nondecreasing if \(x\leq y\) implies \(f(x)\leq f(y)\). This property compares the images of two different inputs. By contrast, a sequence generated by \(f\) is nondecreasing if \(a_n\leq a_{n+1}\) at every index. These are different statements: an increasing function does not by itself make every iteration increase. The first step must point in the appropriate direction.

A useful result established earlier in the course is the Theorem (Convergence of a Monotone Iteration). In particular, for a nondecreasing self-map of a closed bounded interval, an initial step with \(a_1\geq a_0\) yields a nondecreasing iteration; an initial step with \(a_1\leq a_0\) yields a nonincreasing one. The sign-of-the-increment theorem above gives another route: it asks directly whether \(f(x)-x\) has a fixed sign on an invariant interval, without requiring \(f\) itself to be nondecreasing.

Worked Example: A Nested-Radical Recursion

Let \(a_0=0\) and define \(a_{n+1}=\sqrt{2+a_n}\). We first show that the interval \([0,2]\) is invariant. If \(0\leq x\leq2\), then \(2\leq2+x\leq4\), so \(\sqrt{2}\leq f(x)\leq2\); in particular \(f(x)\in[0,2]\). Since \(a_0\in[0,2]\), all the terms lie in this interval.

For \(0\leq x\leq2\), the difference between the next value and the current value can be tested by comparing squares: both \(x\) and \(\sqrt{2+x}\) are nonnegative, and

2+x-x^2=(2-x)(x+1)\geq0.

Thus \(x^2\leq2+x\), which implies \(x\leq\sqrt{2+x}\). The sequence is nondecreasing by the Monotonicity from the Sign of the Increment theorem. It is bounded above by \(2\), so the Monotone Convergence Theorem implies that it converges to some \(L\in[0,2]\).

The first terms are \(a_1=\sqrt{2}\) and \(a_2=\sqrt{2+\sqrt{2}}\). Since the square-root function is continuous on its domain, taking limits in the recurrence gives \(L=\sqrt{2+L}\). Squaring is valid because both sides are nonnegative. Therefore \(L^2-L-2=0\), so \((L-2)(L+1)=0\). The only root in \([0,2]\) is \(L=2\).

Passing the Recursion to the Limit

Monotonicity and a bound can establish that a sequence has a finite limit. To identify that limit, one often uses continuity of the rule. This step is not automatic for an arbitrary function: it is continuity at the limit that permits the recursive equation to pass to the limit.

Theorem (A Continuous Recursive Limit Is a Fixed Point): Suppose \(a_{n+1}=f(a_n)\), \(a_n\to L\in\mathbb{R}\), and \(f\) is continuous at \(L\). Then \(f(L)=L\).

Proof. Because \(a_n\to L\) and \(f\) is continuous at \(L\), we have \(f(a_n)\to f(L)\). The recursion says \(f(a_n)=a_{n+1}\). A shifted convergent sequence has the same limit as the original sequence, so \(a_{n+1}\to L\). Consequently \(f(a_n)\) converges both to \(f(L)\) and to \(L\). Uniqueness of limits gives \(f(L)=L\). \(\square\)

This theorem identifies a necessary property of the limit, not a guarantee that an iteration converges. The order of reasoning matters: first prove convergence, and then use continuity to obtain the fixed-point equation. Solving \(f(x)=x\) by itself does not show that the iterates approach any of its solutions.

Worked Example: A Decreasing Iteration for the Square Root of Three

Start with \(a_0=2\) and define

a_{n+1}=\frac{1}{2}\left(a_n+\frac{3}{a_n}\right).

The rule is defined for positive inputs. Let \(J=[\sqrt{3},2]\), which contains \(a_0\). For \(x\in J\), the difference from the lower endpoint is

f(x)-\sqrt{3} =\frac{x+3/x-2\sqrt{3}}{2} =\frac{(x-\sqrt{3})^2}{2x}\geq0.

Here \(x>0\), so the denominator is positive. Also,

x-f(x)=\frac{x-3/x}{2} =\frac{x^2-3}{2x}\geq0,

because \(x\geq\sqrt{3}\) implies \(x^2\geq3\). Therefore \(\sqrt{3}\leq f(x)\leq x\leq2\), proving that \(J\) is invariant and \(f(x)\leq x\) on \(J\). The sequence is nonincreasing and bounded below, so it converges to a limit \(L\in[\sqrt{3},2]\).

For a check on the arithmetic, \(a_1=(2+3/2)/2=7/4\). Then

a_2=\frac{1}{2}\left(\frac{7}{4}+\frac{3}{7/4}\right) =\frac{1}{2}\left(\frac{49}{28}+\frac{48}{28}\right) =\frac{97}{56}.

The rule is continuous on \(J\), whose elements are positive, so the continuous recursive limit theorem gives \(L=(L+3/L)/2\). Since \(L>0\), this equation is equivalent to \(L^2=3\). The only positive solution is \(L=\sqrt{3}\). Thus the iteration decreases toward \(\sqrt{3}\) while remaining at or above it.

When the Sign Test Is Useful

The increment \(f(x)-x\) can often be factored or simplified, making its sign easier to determine than the direction of the function \(f\) itself. For example, the next rule has a nonnegative increment on \([0,1]\), and the same interval traps every iterate.

Worked Example: Increasing Iterates with a Fixed-Point Limit

Let \(a_0=0\) and set \(a_{n+1}=(1+a_n^2)/2\). For \(0\leq x\leq1\),

\frac{1+x^2}{2}-x=\frac{(1-x)^2}{2}\geq0, \qquad 1-\frac{1+x^2}{2}=\frac{(1-x)(1+x)}{2}\geq0.

These inequalities show \(x\leq f(x)\leq1\). Hence \([0,1]\) is invariant, and the iterates are nondecreasing and bounded above by \(1\). For example, \(a_1=1/2\) and \(a_2=(1+1/4)/2=5/8\). By the Monotone Convergence Theorem, \(a_n\to L\) for some \(L\in[0,1]\). Continuity and the recursive limit theorem give \(L=(1+L^2)/2\). Rearranging yields \((L-1)^2=0\), so \(L=1\).

The interval need not always be the full domain of \(f\); it only needs to contain the starting value, remain invariant, and support the needed increment inequality. Choosing a useful interval can require some algebra. It is also important not to infer monotonicity from the first step alone when the rule is not known to preserve order or the increment sign. For instance, on \([0,1]\), the rule \(f(x)=(1-x)^2\) started at \(a_0=0\) gives \(a_1=1\) and \(a_2=0\). The first step increases, but the next decreases.

A reliable analysis therefore separates the tasks. Establish invariance to keep the recursion in a controlled region; determine the sign of \(f(x)-x\) there to prove monotonicity; find a bound to obtain convergence; and, when \(f\) is continuous at the limit, use the recursive equation to identify that limit. The Monotone Convergence Theorem supplies the convergence step, while the sign test and continuity argument explain how the recursive structure produces and identifies the limit.

Check Your Understanding

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

What does it mean for an interval to be invariant under a recursive rule?
Why does \(f(x)\geq x\) on an invariant interval imply that an iteration starting there is nondecreasing?
How does the sign-of-the-increment method differ from a method that assumes \(f\) is nondecreasing?
Why is continuity at the limit needed to conclude that a convergent recursive iteration has a fixed-point limit?
For \(a_{n+1}=(1+a_n^2)/2\) with \(a_0=0\), which inequalities establish that the sequence stays in \([0,1]\) and is nondecreasing?

What You'll Learn