Why Induction Is Useful for Recursive Bounds
A recursively defined sequence is given by an initial value and a rule for producing each next term. To prove a bound for every term, it is not enough to check several values: a proof must explain why the rule continues to produce terms within the claimed bounds, no matter how many steps are taken.
Mathematical induction is well suited to this task. The key is to choose a statement about the terms that is both true at the starting index and strong enough to be preserved by the recurrence. Sometimes that statement is a simple fixed upper or lower bound. In other cases, the useful hypothesis is a pair of bounds or a sharper bound that depends on the index.
The Induction Principle for a Recursive Sequence
Suppose a sequence is defined by \(x_1=a\) and \(x_{n+1}=f_n(x_n)\) for every \(n\in\mathbb{N}\). The recurrence must be defined at each term where it is used. To prove a statement \(P(n)\) for every \(n\geq 1\), induction requires two parts: prove \(P(1)\), then prove that for every \(n\geq 1\), \(P(n)\) implies \(P(n+1)\). These two steps establish \(P(n)\) for all \(n\geq 1\).
For a bound, \(P(n)\) might be \(x_n\leq U\), \(x_n\geq L\), or \(L\leq x_n\leq U\). The recurrence determines what must be shown in the inductive step. For example, if the hypothesis is \(L\leq x_n\leq U\), the step must use that hypothesis to prove \(L\leq f_n(x_n)\leq U\).
This is the induction principle applied to a recursive sequence. The recurrence supplies the link between consecutive cases; induction supplies the reason the link proves the claim at every index.
A Complete Justification
The logic behind induction is worth making explicit. The base case gives the first true instance. The step then passes truth from each index to the next. Repeating that implication reaches every positive integer, so no finite list of numerical checks is being mistaken for a proof.
Check the proposed bound for the initial term, or for the first term in the range being claimed.
Use precisely the bound stated in the induction hypothesis, along with any conditions needed for the recurrence.
Substitute \(x_{n+1}=f_n(x_n)\), then show the resulting expression satisfies the proposed bound at index \(n+1\).
Once the base case and implication are proved, state that the bound holds throughout the claimed range of indices.
Worked Examples
Worked Example: A Lower and Upper Bound After the First Term
Define \(x_1=0\) and \(x_{n+1}=\frac{1}{2+x_n}\) for \(n\geq1\). Prove that \(\frac{2}{5}\leq x_n\leq\frac{1}{2}\) for every \(n\geq2\).
The bound does not hold for \(x_1\), since \(x_1=0<\frac25\). Start instead at \(n=2\). First calculate the term at that index:
Thus \(\frac25\leq x_2\leq\frac12\), which is the base case. Now suppose, for some \(n\geq2\), that \(\frac25\leq x_n\leq\frac12\). Then
All quantities in this inequality are positive. Taking reciprocals reverses the order, so the recurrence gives
Since \(\frac{5}{12}\leq\frac12\), it follows that \(\frac25\leq x_{n+1}\leq\frac12\). The base case and step prove the bound for every \(n\geq2\). As a check on the first step, the recurrence gives \(x_3=\frac{1}{2+1/2}=\frac25\), which satisfies both bounds.
Worked Example: Preserving a Fixed Pair of Bounds
Let \(x_1=\frac32\) and \(x_{n+1}=\frac{x_n^2+2}{3}\) for \(n\geq1\). Prove that \(1\leq x_n\leq2\) for every \(n\geq1\).
For the base case, \(x_1=\frac32\), and \(1\leq\frac32\leq2\). Suppose now that \(1\leq x_n\leq2\). Squaring these nonnegative quantities gives \(1\leq x_n^2\leq4\). Adding \(2\) and dividing by the positive number \(3\) yields
Therefore the same pair of bounds holds at index \(n+1\). Induction proves \(1\leq x_n\leq2\) for all \(n\geq1\). To check the recurrence’s first application directly,
Indeed, \(\frac{12}{12}\leq\frac{17}{12}\leq\frac{24}{12}\), so this computed term satisfies the claimed bounds.
Worked Example: A Bound That Must Depend on the Index
Define \(x_1=1\) and \(x_{n+1}=x_n+\frac{1}{n(n+1)}\) for \(n\geq1\). Prove that \(x_n=2-\frac1n\), and hence that \(1\leq x_n<2\) for every \(n\geq1\).
Use the sharper induction statement \(P(n):x_n=2-\frac1n\). At \(n=1\), \(2-\frac11=1=x_1\), so the statement holds. Suppose \(x_n=2-\frac1n\). Then
This is exactly \(P(n+1)\), so induction proves the formula for every positive integer \(n\). Since \(n\geq1\), we have \(0<\frac1n\leq1\). Therefore \(1\leq2-\frac1n<2\), as required. Substitution checks the formula against the recurrence: \( (2-\frac1n)+\frac{1}{n(n+1)}=2-\frac{1}{n+1}\), and at \(n=1\) it gives \(x_1=1\).
Choosing a Hypothesis the Recurrence Can Preserve
The main work is often choosing the induction statement. A proposed constant bound may be true but too weak to make the inductive step work. The hypothesis must contain enough information to control the recurrence’s next value. Example 1 used two bounds together; Example 3 needed an index-dependent equality to control an increment that shrinks with \(n\).
Before writing the induction step, ask what information about \(x_n\) makes the recurrence yield the desired conclusion about \(x_{n+1}\). If the recurrence includes a denominator, the hypothesis may need to guarantee that the denominator is nonzero and has the required sign. If it includes a square, knowing whether \(x_n\) is nonnegative can matter. A bound should not be used to justify an operation unless its conditions have been checked.
When proving both a lower and an upper bound, it is often efficient to state one combined hypothesis, \(L\leq x_n\leq U\), and prove both inequalities at the next index. This prevents a gap in which an upper bound is assumed while a lower bound needed for the same calculation has not been established.
A Common Induction Mistake
A frequent error is to assume a bound that does not actually control the next recurrence step. For the sequence in Example 3, one might try to prove \(x_n<2\) using only the induction hypothesis \(x_n<2\), and then write:
This conclusion does not follow: adding a positive number to a quantity below \(2\) can produce a number above \(2\). For instance, at \(n=1\), the hypothesis \(x_n<2\) alone would allow \(x_n=\frac74\), but \(\frac74+\frac12=\frac94>2\). That value is not the sequence’s actual first term; it demonstrates that the stated implication is invalid.
What a Bound Does—and Does Not—Show
Once an induction proves \(L\leq x_n\leq U\) for every relevant index, the sequence is bounded below and above by those numbers. This is a statement about all its terms, not a conclusion about where the terms are heading. A bound by itself does not show that the sequence is increasing, decreasing, or convergent. Those are separate claims requiring their own arguments.
Induction is especially valuable here because it turns the recurring structure of the definition into a proof strategy. Each step verifies that the bound survives one more application of the recurrence; the induction principle then extends that one-step reasoning to every term.
Check Your Understanding
For each question, identify the base case and what the recurrence must establish in the inductive step.
- For a sequence defined from \(x_1\), what two parts are needed to prove \(x_n\leq U\) for every \(n\geq1\)?
- In Example 1, why does the bound begin at \(n=2\) rather than \(n=1\)?
- In Example 2, which inequalities follow from \(1\leq x_n\leq2\) before applying the recurrence?
- Why is \(x_n<2\) alone insufficient to prove the upper bound in Example 3?
- What extra condition should be checked before taking reciprocals in an induction step?