From a Recurrence to a Convergence Proof
A recurrence specifies each term of a sequence using earlier terms. For example, a rule of the form \(a_{n+1}=g(a_n)\), together with an initial value \(a_1\), determines the sequence term by term.
It can be tempting to guess what the terms approach and solve \(L=g(L)\). That equation can help identify a possible limit, but it does not show that the sequence converges. A complete argument first establishes convergence, often by proving that the sequence is monotone and bounded. Only then is it justified to use the recurrence to find the limit.
The Convergence Principle
A sequence \((a_n)\) is increasing if \(a_{n+1}\geq a_n\) for every relevant index \(n\), and decreasing if \(a_{n+1}\leq a_n\). It is bounded above if there is a number \(M\) such that \(a_n\leq M\) for every \(n\), and bounded below if there is a number \(m\) such that \(a_n\geq m\) for every \(n\).
For a recursive sequence, these properties are usually proved together. First find an interval that contains the starting value and is preserved by the recurrence. Then compare \(a_{n+1}\) with \(a_n\) for terms in that interval. The interval supplies a bound; the comparison supplies monotonicity.
Why Monotonicity and Boundedness Guarantee a Limit
Here is a proof for an increasing sequence bounded above. Let \(S=\{a_n:n\in\mathbb{N}\}\) be the set of its terms. Since the sequence is bounded above, \(S\) has a least upper bound; call it \(L=\sup S\). We show directly that \(a_n\) approaches \(L\).
For any \(\varepsilon>0\), \(L-\varepsilon\) cannot be an upper bound for \(S\). Therefore some index \(N\) satisfies \(a_N>L-\varepsilon\). Also \(a_N\leq L\), since \(L\) is an upper bound.
For every \(n\geq N\), increasingness gives \(a_n\geq a_N>L-\varepsilon\), while the upper bound gives \(a_n\leq L\).
Thus \(0\leq L-a_n<\varepsilon\) for every \(n\geq N\). This is the definition of \(a_n\to L\).
For a decreasing sequence bounded below, use the greatest lower bound \(L=\inf\{a_n:n\in\mathbb{N}\}\). Given \(\varepsilon>0\), some term satisfies \(a_N<L+\varepsilon\); otherwise \(L+\varepsilon\) would be a lower bound larger than the greatest lower bound. For \(n\geq N\), decreasingness and the lower bound give \(L\leq a_n\leq a_N<L+\varepsilon\). Hence \(|a_n-L|<\varepsilon\), proving convergence in this case as well.
Using the Recurrence After Convergence Is Known
Suppose \(a_{n+1}=g(a_n)\), the sequence converges to \(L\), and \(g\) is continuous at \(L\). The shifted sequence \((a_{n+1})\) has the same limit \(L\). Continuity also gives \(g(a_n)\to g(L)\). Since \(a_{n+1}=g(a_n)\) term by term, their limits agree, so
This is the fixed-point equation for the limit. Its use depends on having already proved convergence and on \(g\) being continuous at the limit. Solving the equation may produce several candidates, so the interval containing the sequence and any other restrictions must also be considered.
Worked Examples
Worked Example: An Increasing Sequence Bounded Above
Let \(a_1=0\) and \(a_{n+1}=\dfrac{a_n+2}{2}\). Prove that the sequence converges and find its limit.
Step 1: Establish an interval bound. The recurrence function is \(g(x)=\dfrac{x+2}{2}\). The initial value satisfies \(0\leq a_1\leq2\). If \(0\leq a_n\leq2\), then
Thus \(0\leq a_{n+1}\leq2\). By induction, every term lies in \([0,2]\), so the sequence is bounded above by \(2\).
Step 2: Prove it is increasing. For every \(n\),
because \(a_n\leq2\). Therefore the sequence is increasing. The Monotone Convergence Theorem proves that it converges.
Step 3: Identify and check the limit. Let its limit be \(L\). The recurrence function is continuous, so
Check by substitution: \(g(2)=\dfrac{2+2}{2}=2\). The candidate satisfies the recurrence’s fixed-point equation and lies in the established interval \([0,2]\). The convergence proof and the recurrence therefore identify the limit as \(2\).
The first few terms, \(0,1,\dfrac32,\dfrac74\), are consistent with the argument, but these calculations alone would not prove convergence.
Worked Example: A Square-Root Recurrence Increasing to Its Limit
Let \(x_1=1\) and \(x_{n+1}=\sqrt{2+x_n}\). Prove convergence and determine the limit.
Step 1: Keep the terms in \([1,2]\). We have \(x_1=1\in[1,2]\). If \(1\leq x_n\leq2\), then \(3\leq2+x_n\leq4\), and hence
Since \(\sqrt{3}>1\), this shows \(x_{n+1}\in[1,2]\). Induction proves that every term lies in this interval.
Step 2: Compare consecutive terms. For \(1\leq x_n<2\), both \(x_n\) and \(\sqrt{2+x_n}\) are nonnegative, so squaring preserves their order. We have
The last product is positive because \(x_n<2\) and \(x_n+1>0\). Also, \(x_n\) cannot equal \(2\): if it did, the recurrence would give \(x_{n+1}=2\), and reversing the recurrence shows that equality at any later term would require an earlier term to be \(2\), contrary to \(x_1=1\). Thus the sequence is strictly increasing. It is bounded above by \(2\), so it converges.
Step 3: Solve the limit equation. If \(x_n\to L\), then \(1\leq L\leq2\). Continuity of the square-root function gives
The roots are \(2\) and \(-1\); the bound \(1\leq L\leq2\) rules out \(-1\). Therefore \(L=2\). Checking the original recurrence, \(\sqrt{2+2}=2\), as required.
Worked Example: A Decreasing Sequence Bounded Below
Let \(y_1=2\) and \(y_{n+1}=\sqrt{1+y_n}\). Prove convergence and find the limit.
Step 1: Identify a useful lower bound. Define \(\phi=\dfrac{1+\sqrt{5}}{2}\). Direct calculation gives \(\phi^2=\phi+1\), so \(\sqrt{1+\phi}=\phi\). Also \(1<\phi<2\): the first inequality follows from \(\sqrt5>1\), and the second from \(\sqrt5<3\). The initial term \(y_1=2\) therefore lies in \([\phi,2]\).
If \(\phi\leq y_n\leq2\), the square-root function is increasing, so
Thus each term remains in \([\phi,2]\), by induction.
Step 2: Prove the sequence is decreasing. For \(y_n>\phi\), both sides being compared are positive, and
Because \(y_n>\phi\), \(y_n^2-y_n-1>0\): the quadratic has roots \(\phi\) and \(\dfrac{1-\sqrt5}{2}<0\), and is positive above its positive root. Hence \(y_{n+1}<y_n\) whenever \(y_n>\phi\). If a term equals \(\phi\), the next term also equals \(\phi\). The sequence is therefore decreasing and bounded below by \(\phi\), so it converges.
Step 3: Identify the limit. Let \(y_n\to L\). Since \(\phi\leq y_n\leq2\), we have \(\phi\leq L\leq2\). Taking limits in the recurrence gives
The second root is negative, while \(L\geq\phi>0\), so \(L=\phi\). Finally, \(\sqrt{1+\phi}=\phi\) because \(\phi^2=1+\phi\) and \(\phi>0\). This verifies the limit in the recurrence.
A Common Mistake: Solving the Fixed-Point Equation Too Soon
A fixed-point equation gives a necessary condition for a limit when the recurrence function is continuous. By itself, it does not establish that the sequence has a limit.
For example, the recurrence \(b_1=2\), \(b_{n+1}=b_n^2\) has fixed-point equation \(L=L^2\), whose solutions are \(L=0\) and \(L=1\). But its terms do not approach either candidate: \(b_1=2\), \(b_2=4\), and \(b_3=16\); moreover \(b_n\geq2\) for every \(n\), and \(b_{n+1}=b_n^2\geq2b_n\), so the terms grow without bound.
The incorrect argument is: “Solve \(L=L^2\), obtain possible limits, and conclude the sequence converges to one of them.” The correction is to prove convergence first, for example by establishing monotonicity and boundedness. Only then may continuity justify substituting the limit into the recurrence.
Putting the Proof Together
For a recurrence \(a_{n+1}=g(a_n)\), a reliable proof follows this order:
- Check the starting value and identify an interval that can contain all terms.
- Show that the recurrence keeps terms in that interval, usually by induction.
- Compare \(a_{n+1}\) and \(a_n\) to prove the sequence is increasing or decreasing.
- Apply the Monotone Convergence Theorem using the corresponding upper or lower bound.
- Use continuity of \(g\) at the limit to obtain \(L=g(L)\).
- Use the established interval to select the valid solution, then substitute it into the recurrence to check it.
The interval and the direction of motion do more than prove convergence: they also help distinguish the actual limit from other solutions of the fixed-point equation. A guessed limit is a useful starting point, but the proof is what makes the conclusion valid.
Check Your Understanding
For each question, distinguish the evidence needed to prove convergence from the calculations used to identify a limit.
- What two properties allow the Monotone Convergence Theorem to guarantee convergence?
- For \(a_{n+1}=\dfrac{a_n+2}{2}\) with \(a_1=0\), how does the interval \([0,2]\) help prove the sequence is increasing?
- Why must convergence be established before taking limits in \(a_{n+1}=g(a_n)\)?
- For the recurrence \(x_{n+1}=\sqrt{2+x_n}\), why does the bound \(1\leq L\leq2\) rule out one solution of the fixed-point equation?
- What is missing from an argument that only solves \(L=g(L)\)?
