Recursive Sequences

How Recursive Sequences Behave

A recursive definition specifies how to generate a sequence, but generating its first few terms does not tell us everything about its later behavior. We may want to know whether all terms stay within fixed bounds, whether the terms increase or decrease, or whether a pattern suggested by the first several terms continues indefinitely. Mathematical induction provides a systematic way to prove such claims.

The previous tutorial introduced first-order recurrences, which use the current term to define the next one. Some important sequences use more than one earlier term. For example, a rule may use the two terms immediately before the one being defined. The number of starting values must be sufficient for the rule to begin.

Definition (Finite-order recursive sequence). A sequence has a recurrence of order $k$, where $k$ is a positive integer, if its initial terms $a_0,\ldots,a_{k-1}$ are specified and a rule gives $a_{n+k}$ from earlier terms for every $n\in\mathbb{N}_0$. A common form is $$ a_{n+k}=G(n,a_n,\ldots,a_{n+k-1}). $$ Thus an order-$k$ recurrence requires $k$ initial values to generate the sequence.

For a first-order recurrence, one initial value is generally enough; for a second-order recurrence, two are needed. This is not merely a convention. At the first step of a second-order rule, the rule needs both $a_0$ and $a_1$ in order to calculate $a_2$. A rule and initial values together provide a procedure, while induction lets us prove properties of every term produced by that procedure.

Keeping Every Term Inside an Interval

A useful first question is whether a recurrence can take a term in a chosen interval and produce another term in the same interval. If it can, then an initial term in that interval guarantees that every later term remains there. Such an interval is called invariant under the update rule.

Theorem (Invariant interval principle). Let $I\subseteq\mathbb{R}$, let $F:I\to I$, and define $x_{n+1}=F(x_n)$ for every $n\in\mathbb{N}_0$, with $x_0\in I$. Then $x_n\in I$ for every $n\in\mathbb{N}_0$.

Proof. Let $P(n)$ be the statement $x_n\in I$. The assumption $x_0\in I$ proves the base case $P(0)$. Suppose $P(n)$ holds, so $x_n\in I$. Since $F$ maps $I$ into itself, $F(x_n)\in I$. The recurrence gives $x_{n+1}=F(x_n)$, so $x_{n+1}\in I$. Thus $P(n)$ implies $P(n+1)$. By the Principle of Mathematical Induction, $x_n\in I$ for every $n\in\mathbb{N}_0$. $\square$

The important check is that the rule preserves the entire interval, not just the first few terms. Once that has been shown, induction applies the same check repeatedly. The principle gives a bound whenever $I$ is a bounded interval: if $I=[A,B]$, then $A\leq x_n\leq B$ for every index.

Worked Example: A Sequence That Alternates Inside an Interval

Let $x_0=1$ and define $x_{n+1}=3-x_n$. Take $I=[1,2]$. If $x\in I$, then $1\leq x\leq2$, so subtracting from $3$ gives $1\leq3-x\leq2$. Therefore the update rule maps $I$ into $I$. Since $x_0=1\in I$, the invariant interval principle gives $x_n\in[1,2]$ for every $n$.

Calculating a few terms shows what happens:

x_0=1,\qquad x_1=3-1=2,\qquad x_2=3-2=1,\qquad x_3=3-1=2.

In fact, the terms alternate between $1$ and $2$. To verify the pattern, if $x_n=1$, then $x_{n+1}=3-1=2$; if $x_n=2$, then $x_{n+1}=3-2=1$. This sequence stays bounded but is not monotone. Being confined to an interval does not, by itself, mean that a sequence consistently increases or decreases.

When the Update Rule Preserves Order

An interval gives a bound, while an order-preserving rule can help prove monotonicity. A function $F$ is nondecreasing on an interval $I$ if $u\leq v$ implies $F(u)\leq F(v)$ for all $u,v\in I$. If a sequence starts by moving upward and its update rule preserves order, each later step continues that direction.

Theorem (Monotonicity from an order-preserving rule). Let $F:I\to I$ be nondecreasing, let $x_0\in I$, and define $x_{n+1}=F(x_n)$. If $x_1\geq x_0$, then $(x_n)$ is nondecreasing. If $x_1\leq x_0$, then $(x_n)$ is nonincreasing.

Proof. We prove the nondecreasing assertion first. The assumed inequality $x_1\geq x_0$ is the first step. Suppose for some $n\geq1$ that $x_n\geq x_{n-1}$. Both terms belong to $I$, because $F$ maps $I$ into itself and $x_0\in I$. Since $F$ is nondecreasing,

x_{n+1}=F(x_n)\geq F(x_{n-1})=x_n.

Thus each inequality $x_n\geq x_{n-1}$ implies the next one. Induction, starting with $x_1\geq x_0$, proves $x_{n+1}\geq x_n$ for every $n\in\mathbb{N}_0$. Hence the sequence is nondecreasing.

For the nonincreasing assertion, start with $x_1\leq x_0$. If $x_n\leq x_{n-1}$, the nondecreasing property of $F$ gives $F(x_n)\leq F(x_{n-1})$, or $x_{n+1}\leq x_n$. Induction proves this inequality for every $n$. Hence the sequence is nonincreasing. $\square$

The hypothesis about the first step matters. An order-preserving rule does not determine whether a sequence increases or decreases on its own: that direction depends on the initial value. The theorem also requires the rule to be nondecreasing on a set containing all the terms. Checking that the rule preserves order only at a few generated values is not enough to apply the theorem.

Worked Example: A Bounded Increasing Nonlinear Sequence

Define $x_0=1$ and $x_{n+1}=\sqrt{2+x_n}$. We first show that the interval $I=[1,2]$ is preserved. If $1\leq x\leq2$, then $3\leq2+x\leq4$, so

1\leq\sqrt{2+x}\leq2.

Thus the update rule maps $[1,2]$ into itself, and $x_0\in[1,2]$. The invariant interval principle proves $1\leq x_n\leq2$ for every $n$.

The update rule is nondecreasing on $[1,2]$: if $u\leq v$, then $2+u\leq2+v$, and taking nonnegative square roots preserves this order. Also,

x_1=\sqrt{2+x_0}=\sqrt{3}\geq1=x_0.

The monotonicity theorem now shows that $(x_n)$ is nondecreasing. For a numerical check, $x_2=\sqrt{2+\sqrt{3}}$, which is greater than $x_1=\sqrt{3}$: both are nonnegative, and $2+\sqrt{3}>3$. We have proved that every term stays between $1$ and $2$ and that the terms never decrease. The Monotone Convergence Theorem, proved later in the course, shows that a bounded monotone sequence converges. Here we have proved boundedness and monotonicity, but not the theorem itself.

Recurrences That Use Earlier Terms

Not every recurrence has the first-order form $x_{n+1}=F(x_n)$. A higher-order rule can depend on several terms, so the one-variable monotonicity theorem above does not automatically apply. The Fibonacci sequence is a standard example: each new term is the sum of the two immediately preceding terms.

Worked Example: The Fibonacci Sequence

Define $F_0=0$, $F_1=1$, and $F_{n+2}=F_{n+1}+F_n$ for $n\in\mathbb{N}_0$. The initial values allow the rule to generate the sequence:

\begin{aligned} F_2&=F_1+F_0=1+0=1,\\ F_3&=F_2+F_1=1+1=2,\\ F_4&=F_3+F_2=2+1=3,\\ F_5&=F_4+F_3=3+2=5,\\ F_6&=F_5+F_4=5+3=8. \end{aligned}

The two initial values are essential: $F_2$ is calculated from both $F_0$ and $F_1$. The terms from $F_1$ onward are positive, and after the initial equality $F_1=F_2$, they increase strictly. Indeed, for $n\geq2$, the recurrence gives $F_{n+1}=F_n+F_{n-1}$. Since $F_{n-1}>0$, it follows that $F_{n+1}>F_n$. Positivity follows by induction: $F_1=F_2=1>0$, and if $n\geq1$ with $F_n,F_{n+1}>0$, then $F_{n+2}=F_{n+1}+F_n>0$.

This example also illustrates why the form of the recurrence matters. The first-order monotonicity theorem concerns a rule that applies a nondecreasing function to the current term. A higher-order recurrence carries more information from one step to the next. To prove its properties, we use the actual recurrence relation and choose an induction statement that accounts for all the terms it uses.

Choosing a Useful Induction Statement

For a first-order recurrence, an induction statement can often concern a single term, such as $x_n\in I$ or $x_{n+1}\geq x_n$. For a higher-order recurrence, a property may involve several consecutive terms. The Fibonacci inequalities above, for instance, use positivity of a preceding term to compare two successive terms.

A few checks at small indices are valuable for finding patterns and catching errors in indexing. They do not prove that a pattern continues. For a proof, identify the statement to establish, check it at the first indices where it is meaningful, and then use the recurrence to show that the required information at earlier indices implies it at the next one. This is the same induction structure used in earlier tutorials, adapted to the data the recurrence actually requires.

It is also useful to keep boundedness and monotonicity separate. The alternating example is bounded but not monotone. Conversely, a monotone sequence need not be bounded. When an interval argument proves boundedness and an order argument proves monotonicity in the same direction, the Monotone Convergence Theorem (proved later in the course) will guarantee convergence. Neither ingredient should be omitted when applying that theorem.

Identify the order of the recurrence.
Count how many earlier terms are used and record the required initial values.

Look for a preserved interval.
Check that the update rule sends every point of the proposed interval back into it.

Check the direction of the first step.
For an order-preserving first-order rule, compare $x_1$ with $x_0$ to determine the possible direction of monotonicity.

Use induction at arbitrary indices.
Apply the recurrence to prove the next case, not just to calculate another sample term.

Keep distinct properties distinct.
Prove boundedness and monotonicity separately before invoking a theorem that requires both.

Key takeaway. A recursive rule generates terms, while induction proves their persistent properties. An invariant interval gives a bound; an order-preserving first-order rule, together with the direction of its first step, can give monotonicity. Higher-order recurrences require enough initial values and arguments suited to the terms they use.

Check Your Understanding

Use the recurrence rules and proof techniques in this tutorial to answer the following questions.

How many initial values are needed for a second-order recurrence, and why?
For $x_0=2$ and $x_{n+1}=4-x_n$, verify that $[1,3]$ is preserved by the update rule. Does this establish that the sequence is monotone?
State the two conditions in the invariant interval principle that ensure every term remains in a set $I$.
For a nondecreasing rule $F:I\to I$, what additional comparison of the first two terms lets the monotonicity theorem prove the sequence is nondecreasing?
Why is boundedness alone not enough to conclude that a sequence converges?

What You'll Learn