Why Decreasing Recurrence Maps Oscillate
A recurrence \(x_{n+1}=f(x_n)\) repeatedly applies the same function to the current term. If \(f\) reverses order, a term above a fixed point is sent below it, and a term below the fixed point is sent above it. The resulting sequence may alternate around the fixed point.
Alternation alone does not tell us whether the sequence converges. It may keep switching between two distinct values, or its successive terms may get closer to a common limit. To distinguish these behaviours, it is useful to study the even-indexed and odd-indexed terms separately.
If \(I\) is invariant and \(x_0\in I\), the recurrence \(x_{n+1}=f(x_n)\) stays in \(I\): each term belongs to the domain where the next application of \(f\) is defined. In particular, if \(I\) is bounded, the resulting sequence is bounded.
Alternation Around a Fixed Point
Suppose \(f\) is strictly decreasing on an invariant interval \(I\), and \(\alpha\in I\) is a fixed point. If \(x_n>\alpha\), strict decrease gives \(f(x_n)<f(\alpha)\), so \(x_{n+1}<\alpha\). If \(x_n<\alpha\), it gives \(x_{n+1}>\alpha\). Thus, unless an iterate equals \(\alpha\), every term lies on the opposite side of \(\alpha\) from the preceding term.
If some term equals \(\alpha\), then all later terms equal \(\alpha\), because \(f(\alpha)=\alpha\). Otherwise, the sequence alternates strictly across the fixed point. This describes the location of consecutive terms, not the size of their separation: alternation does not by itself imply that the sequence approaches \(\alpha\).
Why the Even and Odd Subsequences Matter
Applying a strictly decreasing map twice preserves order. In fact, if \(x<y\), then \(f(x)>f(y)\), and applying \(f\) again reverses that inequality, so \(f(f(x))<f(f(y))\). Define \(g=f\circ f\), meaning \(g(x)=f(f(x))\). The recurrence then gives \(x_{n+2}=g(x_n)\). Consequently, the even-indexed terms and the odd-indexed terms each follow iterations of an increasing map.
Each of these two subsequences is monotone, though their directions depend on their first comparison. If \(x_2\ge x_0\), then \(g\) increasing gives \(x_4=g(x_2)\ge g(x_0)=x_2\), and repeating the argument shows the even subsequence is nondecreasing. If \(x_2\le x_0\), the same reasoning shows it is nonincreasing. Since \(f\) reverses order, the odd subsequence moves in the opposite direction.
The monotone convergence theorem applies to the two subsequences individually, not automatically to the full alternating sequence. If \(f\) is also continuous, and the even and odd subsequences converge to \(a\) and \(b\), respectively, the recurrence implies
These equations allow a common limit \(a=b=\alpha\), but they also allow two different limits. A pair of distinct values \(a\) and \(b\) satisfying these equations forms a two-cycle: the map sends \(a\) to \(b\) and \(b\) to \(a\). Thus, continuity and a fixed-point equation alone do not prove convergence of the sequence to a fixed point.
Worked Example: A Bounded Sequence That Keeps Cycling
Worked Example: A Two-Cycle Around a Fixed Point
Let \(f(x)=1-x\) on \(I=[0,1]\), and take \(x_0=\frac14\). The map is strictly decreasing: if \(x<y\), then \(1-x>1-y\). It maps \(I\) into itself, since \(0\le x\le1\) implies \(0\le1-x\le1\). Its fixed point solves \(x=1-x\), so \(\alpha=\frac12\).
Compute the first terms:
Since \(f(\frac34)=\frac14\) and \(f(\frac14)=\frac34\), the recurrence repeats these two values indefinitely. Every term lies in the bounded interval \([0,1]\), but the sequence does not converge: its even-indexed terms equal \(\frac14\), and its odd-indexed terms equal \(\frac34\). These subsequences have different limits. The example shows explicitly that boundedness and alternation do not imply convergence.
Worked Example: Oscillation That Converges
Worked Example: A Contracting Oscillation
Let \(f(x)=3-\frac12x\) on \(I=[0,4]\), with \(x_0=\frac12\). The function is strictly decreasing. For \(0\le x\le4\), its values lie between \(f(4)=1\) and \(f(0)=3\), so \(f(I)=[1,3]\subseteq[0,4]\). The fixed point satisfies
The first iterates are
To see exactly what happens, measure each term's error from the fixed point. Since \(3-\frac12\alpha=\alpha\),
Repeating this relation gives \(x_n-\alpha=(-\frac12)^n(x_0-\alpha)\). Here \(x_0-\alpha=\frac12-2=-\frac32\), so \(x_n=2+(-\frac12)^n(-\frac32)\). The factor \((-1)^n\) makes the errors alternate in sign, while their magnitudes shrink by a factor of \(\frac12\) each step. Therefore \(x_n\) converges to \(2\). Substitution checks the limiting value: \(f(2)=3-\frac12(2)=2\).
Worked Example: Using Subsequences to Prove Convergence
Worked Example: An Oscillating Nonlinear Recurrence
Consider \(f(x)=\frac{2}{1+x}\) on \(I=[0,2]\), with \(x_0=\frac12\). For \(x<y\) in this interval, \(1+x<1+y\), so \(\frac{2}{1+x}>\frac{2}{1+y}\); hence \(f\) is strictly decreasing. Its values lie in \([\frac23,2]\), which is contained in \(I\). The fixed point in \(I\) satisfies \(x=\frac{2}{1+x}\), or \(x^2+x-2=0\), giving \(x=1\) or \(x=-2\). Only \(\alpha=1\) belongs to \(I\).
Starting from \(x_0=\frac12\), calculate:
The even terms begin \(\frac12,\frac67,\frac{26}{27},\ldots\), below \(1\) and increasing; the odd terms begin \(\frac43,\frac{14}{13},\frac{54}{53},\ldots\), above \(1\) and decreasing. To verify the subsequence behaviour and identify the limits, compose the map with itself:
For \(0\le x\le2\), the denominator \(3+x\) is positive, and
Thus \(g(x)>x\) when \(0\le x<1\), and \(g(x)<x\) when \(1<x\le2\). Also, \(g\) is increasing because it is the composition of two decreasing maps. Since \(x_0=\frac12<1\), the even subsequence \(x_{2n}\) increases under iteration of \(g\). It remains below \(1\), since \(g\) is increasing and \(g(1)=1\). It is therefore bounded and converges to some \(L\in[\frac12,1]\). The odd subsequence is \(x_{2n+1}=f(x_{2n})\), so it decreases and is bounded below by \(1\); it also converges.
Continuity of \(f\) gives \(L=g(L)\). Solving this equation yields
Because \(L\in[\frac12,1]\), we must have \(L=1\). The odd subsequence converges to \(f(L)=f(1)=1\) as well. The two subsequences share a limit, so the full sequence converges to \(1\). The calculations check the fixed-point value: \(\frac{2}{1+1}=1\).
A Common Pitfall: Reversing the Order Incorrectly
A decreasing map reverses inequalities. A common error is to treat it as if it preserved order. For the map \(f(x)=1-x\), the fixed point is \(\frac12\), and \(x_0=\frac14<\frac12\). An incorrect order-preserving argument would claim
But direct calculation gives \(f(\frac14)=\frac34\), so the claimed inequality is false. The correct implication for a strictly decreasing map is \(x<\alpha\Rightarrow f(x)>f(\alpha)=\alpha\). This reversal explains why terms alternate sides of the fixed point.
A second related mistake is to solve \(L=f(L)\) and then declare that the sequence converges to \(L\). Such an equation identifies a possible fixed-point limit, but it does not establish that the sequence has a limit. The two-cycle example is bounded and has a fixed point, yet its iterates do not converge. A convergence argument must also control the terms, for example by proving convergence of both monotone subsequences and showing they have the same limit.
Why the Distinction Matters
Many recursive processes are bounded by the interval in which their map operates. That bound is useful, but boundedness alone does not settle the long-term behaviour. With a decreasing map, checking consecutive terms for monotonicity can also be misleading: strict alternation across a fixed point normally prevents the full sequence from being monotone, even while its even and odd subsequences each move monotonically.
The practical method is to check that the interval is invariant, identify a fixed point when one is available, and use order reversal to locate consecutive terms. Then examine the even and odd subsequences. If both converge to the same value, the full sequence converges; if their limits differ, the sequence oscillates between distinct limiting values and does not converge.
Check Your Understanding
Use the definitions and reasoning in this tutorial to answer the following questions.
- What does it mean for an interval to be invariant under a recurrence map?
- If \(f\) is strictly decreasing and \(f(\alpha)=\alpha\), what can be said about \(x_{n+1}\) when \(x_n>\alpha\)?
- Why are the even-indexed and odd-indexed subsequences monotone when \(f\) is decreasing?
- Can a bounded sequence generated by a decreasing map fail to converge? Explain using the role of the two subsequences.
- In the recurrence \(x_{n+1}=f(x_n)\), what additional conclusion follows if the even and odd subsequences converge to the same limit?
