Why Lower Bounds Matter for Decreasing Recurrences
A recursive rule determines each term from the one before it. If the terms keep decreasing, it is natural to ask whether they approach a definite value. A decreasing sequence cannot continue falling forever if it is bounded below: the monotone convergence theorem guarantees that it converges.
For a recurrence \(x_{n+1}=f(x_n)\), an effective proof often begins by finding a number that no term can pass below. The key step is to prove this bound holds for every term, usually by induction. Once the sequence is known to decrease and remain bounded below, its limit exists. If \(f\) is continuous at that limit, the recurrence identifies the limit as a fixed point of \(f\).
The Convergence Argument
Here, a decreasing sequence means a non-increasing sequence: \(x_{n+1}\le x_n\) for every \(n\). A sequence that is decreasing and bounded below converges by the monotone convergence theorem. In fact, its limit is its infimum.
The infimum conclusion explains the role of a lower bound. The bound shows that the sequence cannot decrease without limit; the infimum describes the value it approaches. A lower bound need not equal the limit. For example, a sequence may have many lower bounds, but only one greatest lower bound.
For a recurrence, a common way to establish the bound is to find an interval that the recurrence map preserves. Suppose \(x_1\ge m\), and \(f(x)\ge m\) whenever \(x\ge m\) in the part of the domain under consideration. Then induction gives \(x_n\ge m\) for every \(n\). To prove decrease, separately show \(f(x_n)\le x_n\) for each term. These two claims work together: the bound keeps the terms in the region where the decrease argument applies.
Choose \(m\) and check that the initial term satisfies \(x_1\ge m\).
Show that \(x_n\ge m\) implies \(x_{n+1}=f(x_n)\ge m\).
Use the established bound to verify \(f(x_n)\le x_n\).
The sequence is decreasing and bounded below, so the monotone convergence theorem applies.
If \(f\) is continuous at the limit, pass to the limit in the recurrence.
Worked Example: A Square-Root Recurrence
Worked Example: A Square-Root Recurrence
Define \(x_1=4\) and \(x_{n+1}=\sqrt{x_n+6}\). Prove that the sequence converges and find its limit.
First, \(x_1=4\ge3\). If \(x_n\ge3\), then $$ x_{n+1}=\sqrt{x_n+6}\ge\sqrt{3+6}=3. $$ Thus induction gives \(x_n\ge3\) for every \(n\).
For any \(x\ge3\), both sides of \(\sqrt{x+6}\le x\) are nonnegative, so we may square without changing the inequality’s direction. The inequality is equivalent to $$ x+6\le x^2 \quad\Longleftrightarrow\quad 0\le x^2-x-6=(x-3)(x+2). $$ This holds for \(x\ge3\). Consequently \(x_{n+1}\le x_n\) for every \(n\). The sequence is decreasing and bounded below by \(3\), so it converges.
Let its limit be \(L\). The map \(f(x)=\sqrt{x+6}\) is continuous for \(x\ge3\). Taking limits in \(x_{n+1}=f(x_n)\) gives $$ L=\sqrt{L+6}. $$ Since \(L\ge3\), squaring gives \(L^2-L-6=0\), or \((L-3)(L+2)=0\). The only root at least \(3\) is \(L=3\).
Check: \(f(3)=\sqrt{3+6}=3\), so the claimed limit satisfies the recurrence’s fixed-point equation. The bounds and decrease already prove convergence; this final check identifies its value.
Why Continuity Identifies the Limit
The step from convergence to a fixed-point equation requires continuity. If \(x_n\to L\), continuity of \(f\) at \(L\) means \(f(x_n)\to f(L)\). But the recurrence says \(f(x_n)=x_{n+1}\), and the shifted sequence \((x_{n+1})\) has the same limit \(L\) as \((x_n)\). Therefore \(f(L)=L\).
The continuity condition matters: without it, one cannot generally replace the limit of \(f(x_n)\) by \(f(L)\). In the examples below, the recurrence maps are continuous throughout the intervals containing the terms and their limits.
Worked Example: A Rational Recurrence
Worked Example: A Rational Recurrence
Let \(x_1=5\) and $$ x_{n+1}=\frac{3x_n+2}{x_n+2}. $$ Show that the sequence converges and determine its limit.
For \(x\ge2\), the denominator \(x+2\) is positive, and $$ \frac{3x+2}{x+2}-2 =\frac{3x+2-2x-4}{x+2} =\frac{x-2}{x+2}\ge0. $$ Since \(x_1=5\ge2\), this calculation shows inductively that \(x_n\ge2\) for every \(n\).
For \(x\ge2\), compare the recurrence value with \(x\): $$ x-\frac{3x+2}{x+2} =\frac{x(x+2)-(3x+2)}{x+2} =\frac{x^2-x-2}{x+2} =\frac{(x-2)(x+1)}{x+2}\ge0. $$ Thus \(x_{n+1}\le x_n\) for every \(n\). The sequence is decreasing and bounded below by \(2\), so it converges to some \(L\ge2\).
The rational map is continuous for \(x\ge2\), since its denominator is nonzero there. Hence $$ L=\frac{3L+2}{L+2}. $$ Multiplying by \(L+2>0\) gives \(L^2+2L=3L+2\), so $$ L^2-L-2=(L-2)(L+1)=0. $$ The roots are \(2\) and \(-1\), and only \(2\) is compatible with \(L\ge2\). Therefore \(L=2\).
Check: \((3\cdot2+2)/(2+2)=8/4=2\), as required. For an intermediate recurrence check, \(x_2=(3\cdot5+2)/(5+2)=17/7\); indeed \(2\le17/7\le5\).
Worked Example: A Rational Map with a Radical Limit
Worked Example: A Rational Map with a Radical Limit
Set \(x_1=4\) and \(x_{n+1}=3-\frac{1}{x_n+1}\). Prove convergence and find the limit.
Let \(r=1+\sqrt3\). Since \(\sqrt3<2\), we have \(r<3<4=x_1\). Also, $$ r+1=2+\sqrt3,\qquad \frac{1}{2+\sqrt3}=\frac{2-\sqrt3}{(2+\sqrt3)(2-\sqrt3)}=2-\sqrt3. $$ It follows that \(3-\frac{1}{r+1}=3-(2-\sqrt3)=r\).
The map \(f(x)=3-\frac{1}{x+1}\) is increasing for \(x\ge r\): if \(y\ge x\ge r\), then $$ f(y)-f(x)=\frac{1}{x+1}-\frac{1}{y+1} =\frac{y-x}{(x+1)(y+1)}\ge0. $$ Thus \(x\ge r\) implies \(f(x)\ge f(r)=r\). Since \(x_1\ge r\), induction gives \(x_n\ge r\) for every \(n\).
For \(x\ge r\), consider $$ x-f(x)=x-3+\frac{1}{x+1}. $$ This expression is zero at \(x=r\). It increases for \(x\ge r\): whenever \(y\ge x\ge r\), $$ \left(y-3+\frac{1}{y+1}\right) -\left(x-3+\frac{1}{x+1}\right) =(y-x)\left(1-\frac{1}{(x+1)(y+1)}\right)\ge0, $$ because \(x,y\ge r>1\). Therefore \(x-f(x)\ge0\) for \(x\ge r\), proving \(x_{n+1}\le x_n\). The sequence converges because it is decreasing and bounded below by \(r\).
Continuity gives \(L=3-\frac{1}{L+1}\), where \(L\ge r\). Multiplication by \(L+1>0\) yields \(L^2-2L-2=0\). Its roots are \(1+\sqrt3\) and \(1-\sqrt3\); the lower bound excludes the second root. Hence \(L=1+\sqrt3\).
Check: the calculation above established \(f(r)=r\), so the value found satisfies the recurrence’s limit equation. The first new term is \(x_2=3-\frac15=\frac{14}{5}\), which is greater than \(r\): indeed \(\frac{14}{5}>1+\sqrt3\) is equivalent to \(\frac95>\sqrt3\), and \(81/25>3\). This agrees with the proved lower bound.
A Common Pitfall: Using a Bound Outside Its Valid Region
A proof that a recurrence decreases for \(x\ge m\) does not establish that it decreases from an initial value below \(m\). The starting term must satisfy the proposed bound, and the recurrence must keep every later term in the region where the inequalities were proved.
Worked Example: Correcting an Invalid Bound Argument
Consider \(x_{n+1}=\sqrt{x_n+6}\) with \(x_1=1\). The inequality \(\sqrt{x+6}\le x\) holds for \(x\ge3\), since \((x-3)(x+2)\ge0\) there. A mistaken argument might use that inequality to claim the sequence decreases and is bounded below by \(3\). But \(x_1=1\) is not in the region \(x\ge3\), and the first step directly contradicts the claimed decrease: $$ x_2=\sqrt{1+6}=\sqrt7>1=x_1. $$ The correction is to check the initial condition before using the bound argument. In this case, the proof for initial value \(4\) cannot be applied to initial value \(1\). A lower-bound and monotonicity proof must be established for the actual starting term.
Check Your Understanding
Use the lower-bound, monotonicity, and continuity steps carefully in each question.
- What does it mean for \(m\) to be a lower bound for a sequence, and how does the infimum differ from an arbitrary lower bound?
- For \(x_{n+1}=\sqrt{x_n+6}\) with \(x_1=4\), which inequalities establish that every term is at least \(3\) and that the sequence decreases?
- Why does a decreasing sequence that is bounded below converge, and what is its limit in terms of its terms?
- Suppose \(x_{n+1}=f(x_n)\), \(x_n\to L\), and \(f\) is continuous at \(L\). Explain why \(L=f(L)\).
- Why is it not enough to solve \(L=f(L)\) when trying to prove that a recursive sequence converges?