A Complete Argument for a Recursive Sequence
A recurrence gives a rule for producing each term from the preceding one. But knowing the rule, or solving its fixed-point equation, does not by itself show that the sequence converges. A useful proof has several linked parts: keep all terms in a suitable range, prove they move in one direction, apply the monotone convergence theorem, and only then use the recurrence to determine the limit.
This workshop follows that pattern in several examples. In each case, the bounds and the direction of motion do more than establish convergence: they also help identify which solution of the fixed-point equation can be the limit.
The Proof Pattern
The recurrence is easiest to manage when its map \(F\) preserves order: whenever \(u\le v\), \(F(u)\le F(v)\). If \(F\) is increasing, it is often possible to prove monotonicity by comparing \(F(x_n)\) with \(x_n\). An invariant interval then ensures that the comparison continues to apply at every step.
Find an interval containing \(x_1\) that the recurrence maps into itself.
Use induction: the initial term is in the interval, and invariance keeps the next term there.
Determine the sign of \(x_{n+1}-x_n=F(x_n)-x_n\) throughout the established range.
Apply the monotone convergence theorem, then use continuity of \(F\) in the recurrence.
For completeness, consider the increasing case. Let \(L=\sup\{x_n:n\in\mathbb N\}\), which exists because the sequence is nonempty and bounded above. Given \(\varepsilon>0\), the number \(L-\varepsilon\) is not an upper bound, so some \(x_N>L-\varepsilon\). For every \(n\ge N\), monotonicity gives \(L-\varepsilon<x_N\le x_n\le L\), hence \(|x_n-L|<\varepsilon\). Thus \(x_n\to L\). For a decreasing sequence bounded below, take \(L=\inf\{x_n:n\in\mathbb N\}\). Some term satisfies \(x_N<L+\varepsilon\), and for \(n\ge N\), \(L\le x_n\le x_N<L+\varepsilon\), so again \(|x_n-L|<\varepsilon\).
When a sequence converges to \(L\) and \(F\) is continuous at \(L\), the recurrence also gives \(x_{n+1}\to F(L)\). But a convergent sequence and its one-place shift have the same limit, so \(x_{n+1}\to L\) as well. Therefore \(L=F(L)\). This equation identifies candidates; the bounds and direction established beforehand determine which candidate is possible.
Worked Example: An Increasing Affine Recurrence
Worked Example: An Increasing Affine Recurrence
Let \(x_1=1\) and \(x_{n+1}=(x_n+4)/3\). Prove convergence and find the limit.
First use the interval \([1,2]\). If \(1\le x_n\le2\), then \[ \frac{5}{3}=\frac{1+4}{3}\le \frac{x_n+4}{3}\le\frac{2+4}{3}=2. \] Thus \(x_{n+1}\in[1,2]\). Since \(x_1=1\) is in this interval, induction gives \(1\le x_n\le2\) for every \(n\ge1\).
For any \(x\in[1,2]\), \[ F(x)-x=\frac{x+4}{3}-x=\frac{4-2x}{3}\ge0. \] Because every \(x_n\le2\), this shows \(x_{n+1}\ge x_n\) for every \(n\). The sequence is increasing and bounded above by \(2\), so the monotone convergence theorem guarantees that it converges.
The first terms are \(x_1=1\), \(x_2=5/3\), and \(x_3=17/9\). Let the limit be \(L\). The map \(F(x)=(x+4)/3\) is continuous, so \[ L=\frac{L+4}{3},\qquad 3L=L+4,\qquad 2L=4,\qquad L=2. \] Check the result: \(F(2)=(2+4)/3=2\), so \(2\) satisfies the recurrence’s fixed-point equation. It also lies in the proved interval \([1,2]\), as required.
Worked Example: A Square-Root Recurrence
Worked Example: A Square-Root Recurrence
Let \(x_1=2\) and \(x_{n+1}=\sqrt{6+x_n}\). Show that the sequence converges and determine its limit.
Use the interval \([2,3]\). For \(x\in[2,3]\), the square-root function is increasing, so \[ \sqrt{8}\le\sqrt{6+x}\le\sqrt{9}=3. \] Also \(\sqrt8>2\), since \(8>4\). Thus \(\sqrt{6+x}\in[2,3]\). The initial term belongs to the interval, so induction proves \(2\le x_n\le3\) for all \(n\).
For \(x\in[2,3]\), both \(x\) and \(\sqrt{6+x}\) are nonnegative. Therefore squaring preserves their order: \[ \sqrt{6+x}\ge x \quad\Longleftrightarrow\quad 6+x\ge x^2 \quad\Longleftrightarrow\quad (x-3)(x+2)\le0. \] The last inequality holds on \([2,3]\), because \(x-3\le0\) and \(x+2>0\). Hence \(x_{n+1}\ge x_n\) for every \(n\). The sequence is increasing and bounded above by \(3\); it therefore converges.
Write its limit as \(L\). The recurrence map \(F(x)=\sqrt{6+x}\) is continuous on this interval, so \(L=\sqrt{6+L}\). Since \(L\ge2\), squaring is valid and gives \[ L^2=6+L,\qquad L^2-L-6=0,\qquad (L-3)(L+2)=0. \] The algebraic candidates are \(3\) and \(-2\), but \(L\in[2,3]\), so only \(L=3\) is possible. Check: \(\sqrt{6+3}=\sqrt9=3\), and this value satisfies the recurrence equation and the established bounds.
Worked Example: A Decreasing Rational Recurrence
Worked Example: A Decreasing Rational Recurrence
Let \(x_1=2\) and \(x_{n+1}=(2x_n+1)/(x_n+2)\). Prove convergence and find the limit.
Take \(I=[1,2]\). For \(x\in[1,2]\), the denominator \(x+2\) is positive and \[ \frac{2x+1}{x+2}\ge1 \quad\Longleftrightarrow\quad 2x+1\ge x+2 \quad\Longleftrightarrow\quad x\ge1. \] Also, \[ \frac{2x+1}{x+2}\le2 \quad\Longleftrightarrow\quad 2x+1\le2x+4, \] which is always true. Thus the interval is invariant. Since \(x_1=2\in I\), induction gives \(1\le x_n\le2\) for every \(n\).
Compare consecutive terms: \[ x_{n+1}-x_n =\frac{2x_n+1}{x_n+2}-x_n =\frac{1-x_n^2}{x_n+2}. \] For \(x_n\in[1,2]\), the denominator is positive and \(1-x_n^2\le0\). Therefore \(x_{n+1}\le x_n\). The sequence is decreasing and bounded below by \(1\), so it converges.
For a numerical check of the recurrence, \(x_2=(2\cdot2+1)/(2+2)=5/4\), and \[ x_3=\frac{2(5/4)+1}{5/4+2} =\frac{7/2}{13/4} =\frac{14}{13}. \] Let \(L\) be the limit. The recurrence map is continuous on \([1,2]\), so \[ L=\frac{2L+1}{L+2},\qquad L(L+2)=2L+1,\qquad L^2=1. \] The roots are \(1\) and \(-1\); the bound \(L\in[1,2]\) selects \(L=1\). Check: \((2\cdot1+1)/(1+2)=1\), and the result is consistent with the sequence’s lower bound.
Why the Bounds Matter
The same recurrence equation can have more than one solution. A solution is only a candidate for the limit; it does not establish that the sequence converges or tell us which solution it approaches. The invariant interval supplies information about every term, and therefore about any limit of those terms. Monotonicity and boundedness provide the convergence proof; continuity then connects the limit to the recurrence.
For a new recurrence, the useful question is not just “What are its fixed points?” First establish where the sequence stays and how it moves. Those facts are what allow the convergence theorem to apply and the fixed-point calculation to become a valid conclusion.
Check Your Understanding
For each question, distinguish carefully between establishing convergence and identifying a possible limit.
- For \(x_1=0\) and \(x_{n+1}=(x_n+6)/4\), find an interval that can be used to prove boundedness, and determine whether the sequence is increasing or decreasing.
- Why does an invariant interval require both that the initial term belong to the interval and that the recurrence map preserve it?
- In the square-root example, why is it valid to square both sides when comparing \(\sqrt{6+x}\) and \(x\) on \([2,3]\)?
- For the rational recurrence, explain why the fixed-point equation alone does not select the limit.
- State the monotonicity and boundedness conditions used to apply the monotone convergence theorem to an increasing sequence.