When a Recurrence Changes Direction
A recursive sequence is defined by giving one or more starting values and a rule for generating later terms. Some recurrences move their terms toward a limit from alternating sides. Others repeatedly cycle through distinct values and therefore do not settle toward one limit. The signs of the errors and the behavior of terms with particular index patterns can reveal which situation is occurring.
A change in direction does not by itself mean that a sequence diverges. An alternating sequence can converge if its terms get closer to one value. By contrast, a sequence that keeps repeating distinct values cannot converge.
Alternation in an Affine Recurrence
Consider an affine recurrence of the form \(a_{n+1}=b+ra_n\), where \(b\) and \(r\) are constants. A fixed point \(L\) is a value that the recurrence leaves unchanged: \(L=b+rL\). When \(r\ne 1\), solving this equation gives \(L=\frac{b}{1-r}\).
Subtracting the fixed-point equation from the recurrence shows how the error from \(L\) changes:
Thus the multiplier \(r\) determines both the sign and size of each error. Repeating this relation gives an exact formula.
The condition \(a_1\ne L\) matters: a zero error does not change sign. The magnitude of \(r\) matters too. When \(-1<r<0\), the alternating errors shrink to zero, so the sequence converges to \(L\). When \(r=-1\), a nonzero error keeps the same magnitude. When \(r<-1\), its magnitude grows. In the latter two cases, a sequence starting away from \(L\) cannot settle at a limit.
Why the Error Formula Holds
The error relation can be applied repeatedly, but induction makes the resulting formula precise. For \(n=1\), the proposed formula gives \(a_1-L=r^0(a_1-L)\), which is true. Now suppose it holds for some \(n\). Using the recurrence for the error gives:
This is the formula with \(n+1\) in place of \(n\). Therefore it holds for every \(n\ge1\). In particular, when \(r<0\) and \(a_1-L\ne0\), the factor \(r^{n-1}\) has alternating signs as \(n\) increases. If also \(|r|<1\), its magnitude tends to zero, so the errors tend to zero and \(a_n\) tends to \(L\).
Worked Example: Alternating Terms That Converge
Worked Example: Alternating Terms That Converge
Let \(a_1=0\) and \(a_{n+1}=3-\frac12a_n\). Find the fixed point and describe the sequence’s behavior.
First solve \(L=3-\frac12L\). Adding \(\frac12L\) to both sides gives \(\frac32L=3\), so \(L=2\). The error recurrence is \(a_{n+1}-2=-\frac12(a_n-2)\), and the initial error is \(a_1-2=-2\). Therefore:
Calculating the first terms directly, \(a_1=0\), \(a_2=3-\frac12(0)=3\), \(a_3=3-\frac12(3)=\frac32\), and \(a_4=3-\frac12(\frac32)=\frac94\). Their errors from \(2\) are \(-2,1,-\frac12,\frac14\), alternating in sign and decreasing in magnitude. Since \(\left|-\frac12\right|<1\), the error formula shows that \(a_n-2\to0\), so \(a_n\to2\).
As a check, substituting \(a_n=2\) into the recurrence gives \(3-\frac12(2)=2\), confirming that \(2\) is indeed fixed. The formula also gives \(a_1=2-2=0\), matching the initial value.
Parity Reveals a Persistent Alternation
When a sequence alternates, it is useful to compare its odd-indexed terms with its even-indexed terms. These are two subsequences: one uses indices \(1,3,5,\ldots\), and the other uses \(2,4,6,\ldots\). If both approach the same value, the alternation may be compatible with convergence. If they remain separated at different values, the original sequence cannot have a limit.
The key fact follows directly from the definition of a sequence limit. If \(a_n\to L\), then every subsequence also tends to \(L\): for any \(\varepsilon>0\), all terms \(a_n\) with sufficiently large \(n\) satisfy \(|a_n-L|<\varepsilon\). A subsequence has increasing indices, so its terms eventually have indices beyond that same threshold. Consequently, if two subsequences have different limits, the original sequence cannot converge.
Worked Example: A Two-Term Cycle
Worked Example: A Two-Term Cycle
Let \(a_1=0\) and \(a_{n+1}=2-a_n\). Determine whether the sequence converges.
The first terms are \(a_1=0\), \(a_2=2-0=2\), \(a_3=2-2=0\), and \(a_4=2-0=2\). The recurrence returns to the starting value after two steps, so the sequence repeats \(0,2,0,2,\ldots\). Equivalently, its fixed point is \(L=1\), and the error relation is \(a_{n+1}-1=-(a_n-1)\). The initial error is \(-1\), so the errors alternate between \(-1\) and \(1\) without shrinking.
The odd-indexed terms are all \(0\), while the even-indexed terms are all \(2\). These two subsequences have different limits, so the original sequence cannot converge. This conclusion is also consistent with the recurrence: if its terms approached a limit \(A\), the limit laws would give \(A=2-A\), hence \(A=1\), but the terms never approach \(1\). For a direct check, every term is either \(0\) or \(2\), so its distance from \(1\) is always \(1\).
Cycles Longer Than Two Terms
A recurrence can repeat a block of three or more terms. If a state in the recurrence returns to its starting state, the deterministic rule repeats the same terms from then on. For a first-order recurrence, the state is the current term. For a recurrence using two previous terms, the state is the ordered pair of those terms. A repeating cycle with at least two distinct values prevents convergence: the distinct values recur indefinitely rather than getting arbitrarily close to one common limit.
Worked Example: A Three-Term Cycle
Worked Example: A Three-Term Cycle
Let \(a_1=1\), \(a_2=-1\), and \(a_{n+2}=-a_{n+1}-a_n\). Find the pattern and decide whether the sequence converges.
Use the recurrence one term at a time:
The first six terms are \(1,-1,0,1,-1,0\). At \(a_4,a_5\), the pair of consecutive terms is \((1,-1)\), exactly the starting pair \((a_1,a_2)\). Because each later term is determined by the preceding pair, the same calculation repeats. The sequence has period \(3\).
The terms at indices \(1,4,7,\ldots\) are all \(1\), while those at indices \(2,5,8,\ldots\) are all \(-1\). Since these subsequences have different limits, the sequence does not converge. As a recurrence check, the next term after \(a_6=0\) is \(a_7=-a_6-a_5=-0-(-1)=1\), as the cycle predicts.
Common Pitfalls
Pitfall 1: Assuming every alternating sequence diverges. In the first worked example, the errors alternate but shrink to zero, so the sequence converges. To decide convergence, track both the sign and the magnitude of the errors.
Pitfall 2: Saying a negative multiplier always makes the terms alternate. Consider \(a_{n+1}=1-\frac12a_n\) with \(a_1=\frac23\). The fixed point satisfies \(L=1-\frac12L\), so \(L=\frac23\). Since \(a_1=L\), the error is zero and every term equals \(\frac23\). The sequence does not alternate between distinct values. The correct condition for sign-changing errors is \(r<0\) and \(a_1\ne L\).
Pitfall 3: Checking only a few terms of a cycle. Several terms may suggest a pattern, but a reliable argument checks that the recurrence reproduces the same state or establishes a formula that applies to every index. The three-term example verifies the returned pair; that is why the repetition continues.
Why These Patterns Matter
For a recursive sequence, calculating terms can reveal a pattern, but the recurrence explains why the pattern persists. An error formula shows whether alternating deviations shrink, stay the same size, or grow. Parity separates odd and even behavior, and a returned state explains a repeating cycle. These tools help distinguish a sequence that approaches a limit by switching sides from one that never settles at a single value.
Check Your Understanding
Use the recurrence or the pattern of its terms to justify each answer.
- For \(a_{n+1}=4-\frac13a_n\) with \(a_1=0\), find the fixed point and state whether the errors alternate. Does the sequence converge?
- For \(a_{n+1}=6-a_n\) with \(a_1=1\), calculate the first four terms and determine whether the sequence converges.
- Why is the condition \(a_1\ne L\) needed when asserting that a negative multiplier makes the errors change sign?
- A sequence has odd-indexed terms tending to \(3\) and even-indexed terms tending to \(5\). Can the sequence converge? Explain.
- In a recurrence that uses the two preceding terms, what should be checked to justify that an observed three-term pattern continues indefinitely?
