Why One Comparison Can Determine a Whole Sequence
A recursively defined sequence is generated by repeatedly applying the same function. If that function preserves order, comparing two consecutive terms can reveal the direction of every later step. The key is to separate two questions: does the recurrence map preserve comparisons, and what is the comparison between the first two terms?
Knowing only that a map is increasing is not enough to conclude that its sequence is increasing. The initial comparison matters too. Once that comparison is known, however, an order-preserving map lets us carry it forward one step at a time.
Order-Preserving Maps
Let \(I\) be an interval of real numbers, and let \(f:I\to I\). The recurrence \(x_{n+1}=f(x_n)\) defines a sequence as long as its initial value and all subsequent terms lie in \(I\). For the results below, it is enough to assume that every term being considered belongs to \(I\).
Every strictly increasing function is order-preserving, but an order-preserving function need not be strictly increasing. For example, a constant function preserves weak inequalities but can turn two distinct inputs into equal outputs.
The relevant property is about the function on the interval containing the sequence terms. A function might preserve order on one interval and fail to do so on another. For instance, \(f(x)=x^2\) is strictly increasing on \([0,\infty)\), but it is not order-preserving on all of \(\mathbb{R}\).
The Propagation Principle
The theorem says that the initial comparison repeats at each step. The sequence is nondecreasing if its first step is nondecreasing; it is strictly increasing if the map also preserves strict inequalities and the first step is strict.
Check whether \(x_1\leq x_2\) or \(x_1<x_2\). The recurrence map alone does not settle this.
Since \(x_{n+1}=f(x_n)\), an order-preserving map carries \(x_n\leq x_{n+1}\) to \(f(x_n)\leq f(x_{n+1})\).
The new comparison is \(x_{n+1}\leq x_{n+2}\), so it advances the sequence by one index.
Why the Induction Works
Here is the complete induction proof. Assume the hypotheses of the theorem and first suppose \(x_1\leq x_2\). We prove the statement \(x_n\leq x_{n+1}\) for every positive integer \(n\).
Base case: For \(n=1\), the claim is exactly the assumed comparison \(x_1\leq x_2\).
Inductive step: Suppose \(x_n\leq x_{n+1}\) for some \(n\in\mathbb{N}\). Both terms lie in \(I\), and \(f\) is order-preserving there, so
By the recurrence, \(f(x_n)=x_{n+1}\) and \(f(x_{n+1})=x_{n+2}\). Therefore
This proves the inductive step. By mathematical induction, \(x_n\leq x_{n+1}\) for every \(n\in\mathbb{N}\). If \(f\) is strictly increasing and the induction hypothesis is strict, the same reasoning gives \(f(x_n)<f(x_{n+1})\), hence \(x_{n+1}<x_{n+2}\). Starting from \(x_1<x_2\), induction then proves strict increase at every step.
The proof depends on both the map's order property and the fact that the sequence terms are in the interval where that property holds. Without either condition, applying \(f\) to an inequality may not produce the inequality the argument needs.
Worked Examples
Worked Example: An Affine Map Produces a Strictly Increasing Sequence
Consider \(x_1=1\) and \(x_{n+1}=f(x_n)\), where \(f(x)=\frac{x+4}{3}\). The map is strictly increasing on \(\mathbb{R}\): if \(u<v\), then \(\frac{u+4}{3}<\frac{v+4}{3}\), since adding \(4\) and dividing by the positive number \(3\) preserve the inequality.
Compute the initial terms:
Since \(1=\frac{3}{3}<\frac{5}{3}\), we have \(x_1<x_2\). The propagation theorem now gives \(x_n<x_{n+1}\) for every \(n\in\mathbb{N}\).
For a direct check of the next step,
The recurrence calculation agrees with the induction result. Substitution also checks the value: \(f(\frac{5}{3})=\frac{17}{9}=x_3\).
Worked Example: A Map Increasing Only on the Relevant Interval
Let \(x_1=2\) and \(x_{n+1}=x_n^2\). Use \(f(x)=x^2\) on \(I=[1,\infty)\). If \(1\leq u<v\), then \(v^2-u^2=(v-u)(v+u)>0\), so \(f\) is strictly increasing on this interval.
First check that every term remains in \(I\). If \(x_n\geq1\), then \(x_{n+1}=x_n^2\geq1\). Since \(x_1=2\geq1\), induction gives \(x_n\in I\) for every \(n\). Now calculate the first comparison:
The propagation theorem gives \(x_n<x_{n+1}\) for every \(n\in\mathbb{N}\). The next terms illustrate the recurrence:
Each displayed value checks by substitution into \(x_{n+1}=x_n^2\): \(2^2=4\), \(4^2=16\), and \(16^2=256\). The interval matters: the proof uses that the terms are at least \(1\), where the square function preserves strict order.
Worked Example: An Order-Preserving Map May Lose Strictness
Define \(f(x)=\max\{x,0\}\) for \(x\in\mathbb{R}\), and start with \(x_1=-2\). This function is order-preserving: if \(u\leq v\), then taking the larger of each number and \(0\) cannot reverse their order. But it is not strictly increasing, since \(f(-2)=f(-1)=0\).
Compute the recurrence \(x_{n+1}=f(x_n)\):
Thus \(x_1<x_2\), but \(x_2=x_3\). Applying the propagation theorem in its order-preserving form shows that \(x_n\leq x_{n+1}\) for every \(n\); it does not show strict increase. In fact, the recurrence remains at zero: if \(x_n=0\), then \(x_{n+1}=f(0)=0\). The computed values satisfy the recurrence, and they show why strictness requires a strictly increasing map, not merely an order-preserving one.
The Direction Comes from the Initial Step
An increasing recurrence map does not by itself make a sequence increase. It preserves whichever direction the first comparison establishes. If \(x_1\geq x_2\), the same induction works with the inequalities reversed: an order-preserving map carries \(x_n\geq x_{n+1}\) to \(x_{n+1}\geq x_{n+2}\). Consequently, the sequence is nonincreasing. If the map is strictly increasing and \(x_1>x_2\), every step is strictly decreasing.
If \(x_1=x_2\), then \(x_2=f(x_1)=x_1\), so \(f(x_1)=x_1\). The recurrence repeats this same value: \(x_3=f(x_2)=f(x_1)=x_1\), and the same reasoning applies at every later step. Thus the sequence is constant.
A Common Mistake
A frequent error is to reason, “The recurrence map is increasing, so the sequence must be increasing.” This omits the necessary comparison between \(x_1\) and \(x_2\).
For a counterexample, take the strictly increasing map \(f(x)=2x\) and initial value \(x_1=-1\). The recurrence gives
The terms satisfy \(-1>-2>-4>-8\), so the sequence is strictly decreasing, not increasing. The map is indeed strictly increasing, since \(u<v\) implies \(2u<2v\). The correction is to calculate the first comparison: \(x_1>x_2\). Order preservation then propagates that comparison in the decreasing direction. The recurrence checks at each displayed step: \(2(-1)=-2\), \(2(-2)=-4\), and \(2(-4)=-8\).
When This Method Is Useful
This method turns a potentially long list of comparisons into one initial check and an induction argument. It is especially useful when each term is defined by applying the same function to the preceding term. Rather than trying to simplify a formula for \(x_n\), one can study how the function acts on ordered inputs.
The method has a focused conclusion: it establishes that consecutive terms keep a consistent order. By itself, it does not establish that the sequence is bounded or convergent. Those are separate properties requiring their own arguments. Here, the essential checks are the interval of order preservation, the initial comparison, and whether strictness is available.
Check Your Understanding
Use the order-preserving principle and the recurrence definitions to answer these questions.
- State the definition of an order-preserving function on an interval.
- Why must the recurrence terms lie in the interval on which the map is order-preserving?
- If \(f\) is order-preserving and \(x_1\leq x_2\), what inequality holds for every later consecutive pair?
- What additional conditions give strict increase rather than nondecrease?
- For \(x_{n+1}=2x_n\) with \(x_1=-1\), identify the initial comparison and the direction of the sequence. Why does the increasing map not make the sequence increasing?
