Why an Interval Can Control an Entire Recurrence
A recursively defined sequence can be difficult to understand by calculating its terms one at a time. Even when the first few terms lie between two fixed numbers, those calculations do not establish that every later term does. An interval provides a way to prove a bound once and then preserve it at every step.
The key idea is to study the rule that produces the next term. If the recurrence is \(x_{n+1}=f(x_n)\), and applying \(f\) to any point in an interval \(I\) gives another point in \(I\), then starting in \(I\) guarantees that the sequence never leaves it.
For a recurrence \(x_{n+1}=f(x_n)\), this condition is useful only when the initial value is also in \(I\). The map condition and the starting-value condition work together: one keeps the next term in the interval, and the other gets the process started there.
The Invariance Principle
The statement is an induction argument. The condition \(f(I)\subseteq I\) supplies the induction step, while \(x_0\in I\) supplies the base case.
By assumption, \(x_0\in I\).
For an index \(n\geq 0\), suppose \(x_n\in I\).
Since \(f(I)\subseteq I\), the inclusion \(x_n\in I\) implies \(f(x_n)\in I\).
The recurrence gives \(x_{n+1}=f(x_n)\), so \(x_{n+1}\in I\). Induction proves the claim for every index.
This proof also explains why checking only the first few terms is unnecessary once a suitable interval has been found. The same argument applies at every step. The interval may be closed, open, or half-open, but its endpoint conditions must match the actual interval: a value equal to an excluded endpoint is not in that interval.
Worked Example: A Radical Map
Worked Example: Keeping a Radical Recurrence in an Interval
Consider \(x_{n+1}=\sqrt{3+x_n}\), with \(x_0=1\). Prove that every term belongs to \([1,3]\).
First, the square root is defined for every \(x\in[1,3]\), because \(3+x\geq 4>0\). For any such \(x\), the bounds \(1\leq x\leq 3\) give \(4\leq 3+x\leq 6\). Taking nonnegative square roots gives \(2\leq\sqrt{3+x}\leq\sqrt{6}\). Since \(2\geq 1\) and \(\sqrt{6}<3\) (because \(6<9\)), it follows that \(\sqrt{3+x}\in[1,3]\). Thus the map sends \([1,3]\) into itself.
The initial value satisfies \(x_0=1\in[1,3]\). The invariance principle now proves that \(x_n\in[1,3]\) for every \(n\geq0\). The first steps are \(x_1=\sqrt{3+1}=2\) and \(x_2=\sqrt{3+2}=\sqrt{5}\); both lie in \([1,3]\), as the general argument guarantees.
Check: The input \(x_0=1\) produces \(x_1=2\), and \(2\in[1,3]\). More generally, the bounds \(2\leq f(x)\leq\sqrt6<3\) verify the required inclusion for every input in the interval, not just for these first terms.
For radical maps, the domain check is part of the argument: the expression under the square root must be nonnegative throughout the chosen interval. The image estimate must then place the resulting values back inside the interval. In this example, the inequalities give that conclusion directly without requiring a separate test of the map at the interval endpoints.
Worked Example: A Rational Map with a Squared Input
Worked Example: Bounding a Rational Recurrence on \([0,1]\)
Let \(x_{n+1}=\dfrac{x_n^2+1}{x_n^2+2}\), with \(x_0=0\). Show that all terms stay in \([0,1]\).
For \(x\in[0,1]\), we have \(0\leq x^2\leq1\). Hence \(x^2+1\geq1>0\), and \(x^2+2\geq2>0\), so the formula is defined throughout the interval. The numerator is no larger than the denominator, since \(x^2+1\leq x^2+2\). Positivity of the denominator therefore gives \(\dfrac{x^2+1}{x^2+2}\leq1\). The numerator is positive and the denominator is positive, so the quotient is also positive. Consequently, \(0<\dfrac{x^2+1}{x^2+2}\leq1\), which proves that the image lies in \([0,1]\).
The starting value is \(x_0=0\in[0,1]\). The first two terms are \(x_1=\dfrac{0^2+1}{0^2+2}=\dfrac12\) and \(x_2=\dfrac{(1/2)^2+1}{(1/2)^2+2} =\dfrac{1/4+1}{1/4+2} =\dfrac{5/4}{9/4} =\dfrac59\). Both are in \([0,1]\), and the invariance principle proves the same bound for every term.
Check: Substitution of \(x_0=0\) gives \(x_1=1/2\), and substitution of \(x_1=1/2\) gives \(x_2=5/9\). The interval proof also checks that the denominator cannot be zero anywhere in the interval, so the recurrence remains defined at each step.
Worked Example: Choosing a Narrower Interval
Worked Example: A Reciprocal Map on a Bounded Interval
Consider \(x_{n+1}=\dfrac{1}{2+x_n}\), with \(x_0=\dfrac13\). Prove that all terms remain in \([\frac13,\frac12]\).
For \(x\in[\frac13,\frac12]\), the denominator satisfies \(\frac73\leq2+x\leq\frac52\), so it is positive. Taking reciprocals reverses the inequalities between these positive numbers: \(\frac{2}{5}\leq\dfrac{1}{2+x}\leq\frac{3}{7}\). The output interval \([\frac25,\frac37]\) is contained in \([\frac13,\frac12]\): indeed, \(\frac13\leq\frac25\) because \(5\leq6\), and \(\frac37\leq\frac12\) because \(6\leq7\). Thus the chosen interval is invariant.
The initial value \(x_0=\frac13\) is in the interval. Direct substitution gives \(x_1=\dfrac{1}{2+\frac13}=\dfrac{1}{\frac73}=\frac37\), and \(x_2=\dfrac{1}{2+\frac37}=\dfrac{1}{\frac{17}{7}}=\frac7{17}\). For an explicit check, \(\frac13<\frac7{17}\) because \(17<21\), and \(\frac7{17}<\frac12\) because \(14<17\). Both computed terms are therefore in the interval, and induction proves this for every term.
Check: The image estimate places every output between \(\frac25\) and \(\frac37\), which are both inside the stated interval. The denominator is positive throughout that interval, so every recurrence step is defined as well.
How to Verify an Interval Image
The central task is to show that every output \(f(x)\), for \(x\) in the candidate interval, belongs to that same interval. The most reliable approach is to write inequalities that hold for an arbitrary \(x\) in the interval. Checking a few inputs can help suggest a choice, but it cannot replace the argument for all inputs.
- Check the domain first. A radical must have a nonnegative radicand, and a rational expression must have a nonzero denominator for every input under consideration.
- Find bounds valid across the interval. Use the defining inequalities for \(x\) to bound expressions such as \(x^2\), \(a+x\), or a denominator.
- Keep inequality operations valid. Multiplying or dividing an inequality by a quantity requires knowing its sign. Taking reciprocals reverses the order for positive quantities.
- Compare the output bounds with the interval. It is not enough to bound \(f(x)\); the resulting bounds must place \(f(x)\) inside the chosen interval, including any endpoint restrictions.
- Verify the initial value separately. Even an invariant interval gives no conclusion for a recurrence whose initial value lies outside it.
Different intervals can work for the same map, and a useful interval need not be the smallest possible one. A wider interval may be easier to verify, while a narrower one may give a sharper bound. What matters for the invariance argument is the inclusion \(f(I)\subseteq I\) and the membership \(x_0\in I\).
A Common Mistake: Assuming a Plausible Interval Is Invariant
For the map \(f(x)=\sqrt{2+x}\), it may seem reasonable to try \([0,1]\). But for \(x\in[0,1]\), we have \(2\leq2+x\leq3\), so \(\sqrt2\leq f(x)\leq\sqrt3\). Since \(\sqrt2>1\), the outputs are not in \([0,1]\). In fact, starting at \(x_0=0\) gives \(x_1=\sqrt2>1\), so this proposed interval fails immediately.
A related incorrect argument might say that because the input is at most \(1\), the output is also at most \(1\). The actual calculation contradicts that claim: \(x_0=0\) gives \(f(0)=\sqrt2>1\). To repair the choice, use \([1,2]\): for \(x\) in this interval, \(3\leq2+x\leq4\), so \(\sqrt3\leq f(x)\leq2\), which lies inside \([1,2]\). This repair proves invariance for that interval, but it only applies to initial values in \([1,2]\).
Why Invariant Intervals Matter
An invariant interval supplies a uniform bound for every term of a recurrence using one map estimate and one induction. This can establish that the recurrence stays within the part of the real line where its formula is valid, and it can rule out terms escaping beyond specified bounds.
It is also a useful starting point for further analysis: once the terms are known to remain in an interval, other properties can be studied with that information available. The interval argument itself should not be asked to prove more than it establishes. In particular, infinitely many terms inside a bounded interval need not converge, and invariance does not tell us whether successive terms increase or decrease.
Check Your Understanding
For each question, distinguish the map condition from the condition on the initial value.
- State what it means for an interval \(I\) to be invariant under a map \(f\).
- Why are both \(f(I)\subseteq I\) and \(x_0\in I\) needed to conclude that every term stays in \(I\)?
- For \(f(x)=\sqrt{1+x}\), identify the domain check required before testing an interval.
- For \(f(x)=\dfrac{1}{2+x}\), what must be checked before taking reciprocals in an interval estimate?
- Does proving that all terms lie in a bounded invariant interval establish that the sequence converges? Explain briefly.