Why Analyze the Recurrence Function?
A recursive sequence is specified by an initial value and a rule that produces each new term from the preceding one. For example, a recurrence may have the form \(a_{n+1}=g(a_n)\). Calculating several terms can suggest whether the sequence stays bounded or moves consistently upward or downward, but a few calculations do not establish what happens at every step.
A more reliable approach is to study the function \(g\) on an interval containing the initial value. If the function sends that interval back into itself, then every term remains in the interval. If, in addition, \(g(x)-x\) has a consistent sign there, then every step moves in the same direction.
Invariant Intervals
Suppose the sequence is defined by \(a_{n+1}=g(a_n)\) for \(n\geq 1\), with initial value \(a_1\). The recurrence can be used only when each term lies in the domain of \(g\). A useful way to ensure this is to find an interval that contains the initial term and is preserved by the function.
The final claim follows by induction. The initial term is in \(I\). If \(a_n\in I\), invariance gives \(a_{n+1}=g(a_n)\in I\). Thus the next term is also in \(I\), and the argument repeats for every index.
When \(I=[L,U]\), checking that \(g(L)\) and \(g(U)\) lie in the interval is not always enough. It is sufficient if you have also established that \(g\) is monotone on \([L,U]\), because then all its values lie between its endpoint values. Without such a property, you must justify that \(g(x)\in[L,U]\) for every \(x\) in the interval.
How to Prove Monotonicity of the Sequence
To determine the direction of each step, compare a new term with the current term:
This identity is the central test. If every term lies in \(I\), and \(g(x)-x\geq 0\) for all \(x\in I\), then \(a_{n+1}\geq a_n\) for every \(n\), so the sequence is nondecreasing. If \(g(x)-x\leq 0\) throughout \(I\), then the sequence is nonincreasing. Strict inequalities throughout give strict monotonicity.
Justification. Invariance and induction show that \(a_n\in I\) for each \(n\). In the first case, substituting \(x=a_n\) into the assumed inequality gives \(g(a_n)-a_n\geq 0\). Since \(a_{n+1}=g(a_n)\), this is \(a_{n+1}-a_n\geq 0\), or \(a_{n+1}\geq a_n\), for every \(n\). That is precisely the definition of a nondecreasing sequence. The second case gives \(a_{n+1}-a_n\leq 0\) for every \(n\), which is precisely a nonincreasing sequence.
A Second Monotonicity Method
Sometimes it is easier to compare the first two terms than to study \(g(x)-x\) throughout an interval. If \(g\) is increasing on an invariant interval and \(a_2\geq a_1\), then the recurrence preserves that comparison. Indeed, whenever \(a_n\geq a_{n-1}\), increasingness gives \(g(a_n)\geq g(a_{n-1})\), so \(a_{n+1}\geq a_n\). Induction then proves the sequence is nondecreasing. If \(a_2\leq a_1\), the same reasoning proves it is nonincreasing.
This method requires \(g\) to be increasing on the interval. An increasing function does not, by itself, guarantee that the sequence increases: the first comparison \(a_2\geq a_1\) (or \(a_2\leq a_1\)) must also be checked. The sign test using \(g(x)-x\) is often more direct and does not require \(g\) itself to be increasing.
Worked Examples
Worked Example: A Nondecreasing Sequence in a Closed Interval
Consider \(a_1=1\) and \(a_{n+1}=g(a_n)\), where \(g(x)=\frac{x+4}{3}\). Prove that the terms stay in \([1,2]\) and are nondecreasing.
First check invariance. For \(x\in[1,2]\), adding 4 and dividing by 3 gives \(g(x)\in[\frac{1+4}{3},\frac{2+4}{3}]=[\frac53,2]\subseteq[1,2]\). Thus \([1,2]\) is invariant. Since \(a_1=1\in[1,2]\), induction shows every term lies in \([1,2]\).
Next calculate the change: \(g(x)-x=\frac{x+4}{3}-x=\frac{4-2x}{3}\). For \(x\in[1,2]\), \(4-2x\geq0\), so \(g(x)-x\geq0\). The monotonicity result therefore proves that the sequence is nondecreasing.
The first terms illustrate the rule: \(a_1=1\), \(a_2=g(1)=\frac53\), \(a_3=g(\frac53)=\frac{17}{9}\), and \(a_4=g(\frac{17}{9})=\frac{53}{27}\). The checks \(1\leq\frac53\leq2\), \(\frac53\leq\frac{17}{9}\leq2\), and \(\frac{17}{9}\leq\frac{53}{27}\leq2\) agree with the proof. Substitution verifies the recurrence at the last step: \((\frac{53}{27}+4)/3=\frac{161}{81}=\frac{53}{27}\)? This equality is false, so the term must be recalculated: \((\frac{17}{9}+4)/3=(\frac{53}{9})/3=\frac{53}{27}\), as stated. The recurrence check is \(g(a_3)=\frac{53}{27}=a_4\).
Worked Example: A Nondecreasing Sequence with a Squared Recurrence
Let \(a_1=\frac12\) and \(a_{n+1}=g(a_n)\), where \(g(x)=\frac{x^2+1}{2}\). Prove that the terms stay in \([\frac12,1]\) and are nondecreasing.
For \(x\in[\frac12,1]\), we have \(\frac14\leq x^2\leq1\). Therefore \(g(x)=\frac{x^2+1}{2}\in[\frac58,1]\subseteq[\frac12,1]\). The interval is invariant and contains \(a_1\), so induction puts every term in it.
For monotonicity, factor the change: \(g(x)-x=\frac{x^2+1-2x}{2}=\frac{(x-1)^2}{2}\geq0\). Thus every step is nonnegative and \((a_n)\) is nondecreasing.
Compute several terms to check the arithmetic. First, \(a_1=\frac12\), so \(a_2=((\frac12)^2+1)/2=(\frac14+1)/2=\frac58\). Then \(a_3=((\frac58)^2+1)/2=(\frac{25}{64}+1)/2=\frac{89}{128}\). Next, \(a_4=((\frac{89}{128})^2+1)/2=(\frac{7921}{16384}+\frac{16384}{16384})/2=\frac{24305}{32768}\).
These values lie in the interval: \(\frac12\leq\frac58\leq1\), \(\frac12\leq\frac{89}{128}\leq1\), and \(\frac12\leq\frac{24305}{32768}\leq1\). Their comparisons also agree with the theorem: \(\frac58-\frac12=\frac18>0\), \(\frac{89}{128}-\frac58=\frac9{128}>0\), and \(\frac{24305}{32768}-\frac{89}{128}=\frac{1521}{32768}>0\). Substitution into \(g\) gives exactly \(a_2,a_3,a_4\) as computed, checking the recurrence.
Worked Example: A Nonincreasing Sequence in a Closed Interval
Let \(a_1=2\) and \(a_{n+1}=g(a_n)\), where \(g(x)=\frac{x+1}{2}\). Prove that the sequence stays in \([1,2]\) and is nonincreasing.
For \(x\in[1,2]\), \(g(x)\in[1,\frac32]\), which is contained in \([1,2]\). Hence the interval is invariant, and \(a_1\in[1,2]\), so all terms remain there. Also, \(g(x)-x=\frac{x+1}{2}-x=\frac{1-x}{2}\leq0\) for \(x\in[1,2]\). It follows that the sequence is nonincreasing.
Direct calculation gives \(a_1=2\), \(a_2=g(2)=\frac32\), \(a_3=g(\frac32)=\frac54\), and \(a_4=g(\frac54)=\frac98\). Each value lies in \([1,2]\), and \(2\geq\frac32\geq\frac54\geq\frac98\). The recurrence checks exactly: \((\frac54+1)/2=\frac98=a_4\).
Common Pitfalls
Pitfall 1: Checking only the endpoints of an interval. A function need not stay between its endpoint values unless its behavior on the interval justifies that conclusion. For example, on \([0,1]\), the function \(g(x)=8x(1-x)\) has \(g(0)=0\) and \(g(1)=0\), both in \([0,1]\), but \(g(\frac12)=2\), which is outside the interval. The endpoint check alone does not prove invariance. To correct the argument, establish a bound for all \(x\) in the interval, or first prove a property such as monotonicity that makes endpoint values sufficient.
Pitfall 2: Assuming an increasing recurrence creates an increasing sequence. An increasing function only preserves an existing comparison between inputs. The comparison \(a_2\geq a_1\) still needs to be shown. Conversely, a decreasing function does not generally produce a monotone sequence: \(g(x)=3-x\) maps \([1,2]\) into itself, but with \(a_1=1\) the terms are \(1,2,1,2,\ldots\). Check the sign of \(g(x)-x\) or use increasingness together with the direction of the initial comparison.
What These Results Establish
An invariant interval gives a uniform bound on every term, and a consistent sign for \(g(x)-x\) gives a direction of motion. Together, these facts can establish that a recursive sequence is bounded and monotone. They do not, by themselves, identify a limit or solve an equation for one. Their value is that they provide a rigorous description of the sequence’s behavior at every step, rather than a guess based on a finite list of terms.
Check Your Understanding
For each question, identify the interval or sign information that would justify your conclusion.
- For \(a_1=0\) and \(a_{n+1}=\frac{a_n+2}{3}\), show that \([0,1]\) is invariant. What sign does \(g(x)-x\) have on this interval?
- State the induction step needed to prove that an invariant interval contains every term of a recurrence.
- For \(g(x)=\frac{x^2+1}{2}\), why does \(g(x)-x\geq0\) prove the sequence is nondecreasing once all its terms are in the relevant interval?
- What additional condition, besides \(g\) being increasing, lets you use increasingness to prove a sequence is nondecreasing?
- Why do the values of \(g\) at the two endpoints not always suffice to prove that an interval is invariant?
