From Monotone Sequences to Recursive Approximations
The Monotone Convergence Theorem turns two manageable facts—monotonicity and a bound—into convergence. This is especially useful when the terms are defined recursively. A recursion may not give an explicit formula for its terms, but its defining rule can make it possible to check whether each term moves in one direction and remains within a fixed interval.
Once convergence is established, a second question arises: can the recurrence identify the limit? Often it can. If the recurrence uses polynomial or rational operations, the limit laws allow us to pass to the limit in the recurrence and obtain an equation for the limit. These two steps—prove convergence first, then identify the limit—are distinct and both require justification.
A Monotone Iteration Principle
Proof. Because \(f\) maps \(I\) into itself and \(x_0\in I\), induction shows that \(x_n\in I\) for every \(n\). Suppose first that \(x_0\leq x_1\). We prove by induction that \(x_n\leq x_{n+1}\) for all \(n\). The inequality holds at \(n=0\) by assumption. If \(x_n\leq x_{n+1}\), the fact that \(f\) is nondecreasing gives
Thus the sequence is nondecreasing. It is bounded above by \(B\), since every term belongs to \(I=[A,B]\). The Monotone Convergence Theorem therefore gives convergence to a finite real number.
Now suppose \(x_1\leq x_0\). The base case for nonincreasing behavior holds. If \(x_{n+1}\leq x_n\), applying \(f\) gives \(x_{n+2}=f(x_{n+1})\leq f(x_n)=x_{n+1}\). The sequence is therefore nonincreasing. It is bounded below by \(A\), so the Monotone Convergence Theorem again gives convergence to a finite real number. This proves both cases. \(\square\)
The theorem is a practical way to handle an iteration: establish that the rule preserves the interval and preserves order, then check the direction of the first step. The initial comparison determines the direction of every later step.
When a Limit Must Satisfy the Recurrence
Convergence alone does not automatically allow every operation in a recurrence to pass to the limit. The following result records a common safe case, using the polynomial and quotient limit laws established earlier in the course.
Proof. Since \(a_n\to L\), the subsequence \(a_{n+1}\) also converges to \(L\), by the theorem on subsequences of a convergent sequence. The polynomial limit law gives \(P(a_n)\to P(L)\) and \(Q(a_n)\to Q(L)\). Because \(Q(L)\neq0\), the quotient limit law gives
But the recurrence says that the sequence on the left is \(a_{n+1}\), which converges to \(L\). Uniqueness of limits therefore gives \(L=P(L)/Q(L)\), as required. \(\square\)
For a polynomial recurrence \(a_{n+1}=P(a_n)\), the same conclusion follows directly from the polynomial limit law: \(L=P(L)\). In either case, the recurrence yields an equation only after convergence has been established and the relevant limit law's hypotheses have been checked.
Worked Examples: Finding Limits of Iterations
Worked Example: A Nested-Radical Sequence
Define \(x_0=1\) and \(x_{n+1}=\sqrt{2+x_n}\). We first check that the iteration remains in \([1,2]\). If \(1\leq x_n\leq2\), then \(3\leq2+x_n\leq4\), so \(1\leq x_{n+1}\leq2\). Since \(x_0\in[1,2]\), induction proves that all terms lie in this interval.
The function \(f(x)=\sqrt{2+x}\) is nondecreasing on \([1,2]\): if \(x\leq y\), then \(2+x\leq2+y\), and the nonnegative square root preserves this order. Also, \(x_0=1\leq x_1=\sqrt{3}\). The Convergence of a Monotone Iteration Theorem shows that \((x_n)\) is nondecreasing and converges to some \(L\in[1,2]\).
The limit is positive, so the limit law for roots applied to \(2+x_n\to2+L\) gives \(\sqrt{2+x_n}\to\sqrt{2+L}\). Taking limits in the recurrence yields \(L=\sqrt{2+L}\). Both sides are nonnegative, so squaring gives \(L^2=2+L\). Factoring and solving gives
The possible roots are \(2\) and \(-1\), but \(L\in[1,2]\). Therefore \(L=2\). Notice that the interval bound is useful twice: it proves convergence and rules out the algebraic root \(-1\).
Worked Example: Newton's Method for the Square Root of Three
Set \(x_0=2\) and define \(x_{n+1}=(x_n+3/x_n)/2\). We show directly that the terms decrease while staying above \(\sqrt{3}\). If \(x_n\geq\sqrt{3}\), then \(x_n>0\), and exact rearrangement gives
Thus \(x_{n+1}\geq\sqrt{3}\). Since \(x_0=2\geq\sqrt{3}\), induction shows that every term is positive and at least \(\sqrt{3}\). Moreover,
because \(x_n^2\geq3\) and \(2x_n>0\). The sequence is nonincreasing and bounded below, so the Monotone Convergence Theorem gives a finite limit \(L\), with \(L\geq\sqrt{3}>0\).
The quotient limit law applies because the denominator \(x_n\) is never zero and the limit \(L\) is nonzero. Taking limits in the recurrence gives \(L=(L+3/L)/2\). Multiplying by \(2L\), which is positive, yields \(2L^2=L^2+3\), so \(L^2=3\). Since \(L>0\), we conclude \(L=\sqrt{3}\).
For an initial numerical check, the first step is \(x_1=(2+3/2)/2=7/4\), which is less than \(x_0=2\) and still greater than \(\sqrt{3}\). The general inequalities above, rather than this one calculation, establish those properties for every term.
Worked Example: A Rational Iteration and a Positive Fixed Point
Let \(\alpha=(\sqrt{5}-1)/2\), so \(\alpha>0\), \(\alpha<1\), and \(\alpha^2+\alpha=1\). Define \(x_0=0\) and
On \([0,\alpha]\), the denominator is positive. If \(0\leq x\leq y\leq\alpha\), direct subtraction gives
Thus the defining function is nondecreasing on this interval. Also, \(\alpha\) is a fixed point of the function, since \(\alpha^2+\alpha=1\) implies \(1+\alpha=\alpha(2+\alpha)\). The function maps \([0,\alpha]\) into itself: its values are at least \(f(0)=1/2>0\), and monotonicity gives \(f(x)\leq f(\alpha)=\alpha\). Since \(x_0=0\in[0,\alpha]\) and \(x_1=1/2\geq x_0\), the Monotone Iteration Theorem proves that \((x_n)\) is nondecreasing and converges to some \(L\in[0,\alpha]\).
The rational recurrence theorem applies with \(P(x)=1+x\) and \(Q(x)=2+x\), whose denominator is nonzero on \([0,\alpha]\). Hence \(L=(1+L)/(2+L)\). Since \(2+L>0\), multiplication gives \(L(2+L)=1+L\), or \(L^2+L-1=0\). Its roots are \((-1+\sqrt{5})/2=\alpha\) and \((-1-\sqrt{5})/2<0\). As \(L\geq0\), the limit is \(\alpha\).
Why Monotonicity Does Not Always Identify the Limit
A common mistake is to assume that any convergent iteration \(x_{n+1}=f(x_n)\) must have a limit satisfying \(L=f(L)\). That conclusion needs a reason for passing the limit through \(f\), such as the polynomial or rational limit laws used above. The iteration theorem itself assumes only that \(f\) is nondecreasing and maps an interval into itself; it does not assume continuity.
For example, on \([0,1]\), define \(f(x)=(x+1/2)/2\) when \(0\leq x<1/2\), and \(f(x)=1\) when \(1/2\leq x\leq1\). This function is nondecreasing and maps \([0,1]\) into itself. Starting at \(x_0=0\), its iterates satisfy \(x_n=\tfrac12(1-2^{-n})\). Indeed, this formula gives \(x_0=0\), and whenever it holds, \(x_n<1/2\) and \(f(x_n)=\tfrac12(1-2^{-(n+1)})\). The sequence increases to \(1/2\), but \(f(1/2)=1\), not \(1/2\). The recurrence's limit is not a fixed point.
In applications, keep the logic in order: first verify the interval and monotonicity conditions, then invoke the Monotone Convergence Theorem, and only then pass to the limit in the recurrence using a valid limit law. That separation makes recursive convergence proofs both reliable and easier to check.
Check Your Understanding
Use the iteration principle and the examples to answer the following questions.
- Why does a nondecreasing function preserve the direction of the first step throughout an iteration?
- In the nested-radical example, which interval contains every term, and how does it help identify the limit?
- Why must the limit in Newton's method be nonzero before the quotient limit law can be used?
- What equation does a convergent sequence satisfying \(a_{n+1}=P(a_n)\) obey when \(P\) is a polynomial?
- In the final example, what prevents the limit from being a fixed point of the defining function?