Calculus II: Sequences Defined Recursively

In engineering and scientific computing, you rarely receive answers in a neat, closed-form box. More often, you start with an initial guess and iteratively refine it until the solution converges. This process is mathematically described by recursively defined sequences, where each term is calculated from its predecessors. Mastering these sequences is not just an academic exercise; it is fundamental to understanding numerical algorithms, modeling dynamic systems, and analyzing the stability of iterative methods used in everything from structural analysis to machine learning.

What is a Recurrence Relation?

A recurrence relation is an equation that defines a sequence where each term is expressed as a function of one or more preceding terms. Unlike an explicit formula like $a_n=n^2$, which gives you the $n$-th term directly, a recursive definition requires you to compute step-by-step. The general form is $a_{n+1}=f(a_n)$, often accompanied by an initial condition $a_0$ or $a_1$.

For example, consider the sequence defined by $a_{n+1}=\frac{1}{2}{a}_n+3$ with $a_0=1$. To compute terms, you simply apply the rule repeatedly: $a_1=\frac{1}{2}(1)+3=3.5$ $a_2=\frac{1}{2}(3.5)+3=4.75$ $a_3=\frac{1}{2}(4.75)+3=5.375$

This iterative computation is the essence of many numerical methods. Your first task with any recursive sequence is to generate several terms. This often reveals patterns regarding the sequence's growth, decline, or oscillation, providing crucial intuition about its long-term behavior.

Analyzing Behavior: Boundedness and Monotonicity

Before we can discuss convergence, we must describe a sequence's behavior using two key properties: boundedness and monotonicity. These are the diagnostic tools that tell us if a sequence is "well-behaved" enough to settle at a limit.

A sequence $\{a_n\}$ is bounded if there exist real numbers $m$ and $M$ such that $m\le a_n\le M$ for all $n$. Think of it as the sequence existing within a fixed vertical corridor. A sequence is monotone if it is entirely non-decreasing ($a_{n+1}\ge a_n$) or entirely non-increasing ($a_{n+1}\le a_n$). It consistently moves in one direction (or stays flat), never reversing course.

Proving these properties often requires induction. For the sequence $a_{n+1}=\frac{1}{2}{a}_n+3,a_0=1$, you might suspect it's increasing and bounded above. To prove it's increasing, show $a_{n+1}>a_n$ for all $n$. To prove it's bounded above, guess a potential upper bound (like 6) and use induction to show $a_n<6$ for all $n$. Establishing these traits is the critical step before applying the powerful convergence theorem that follows.

The Monotone Convergence Theorem

The Monotone Convergence Theorem (MCT) is a cornerstone of real analysis and a primary tool for proving convergence for recursive sequences. It states: Every sequence that is both monotone and bounded must converge to a limit.

This theorem is powerful because it guarantees convergence without requiring you to guess the limit's value beforehand. You simply prove two things:

1. Monotonicity: The sequence is always increasing or always decreasing.
2. Boundedness: The sequence is trapped between two finite numbers.

If you can establish both, the MCT assures you that ${\lim }_{n\to \infty }{a}_n=L$ for some real number $L$. For our running example, having shown the sequence is increasing and bounded above by 6, the MCT guarantees it converges to some limit $L$. The theorem doesn't tell us what $L$ is, but it confirms our iterative process is stable and heading toward a specific target.

Finding the Limit of a Recursive Sequence

Once the Monotone Convergence Theorem (or other analysis) confirms convergence, you can find the actual limit $L$. A crucial property of convergent recursive sequences is that the limit must be a fixed point of the recurrence function. If $a_{n+1}=f(a_n)$ and ${\lim }_{n\to \infty }{a}_n=L$, then taking the limit on both sides gives: $$L=\underset{n\to \infty }{\lim }{a}_{n+1}=\underset{n\to \infty }{\lim }f(a_n)=f(L)$$ The last step, $\lim f(a_n)=f(L)$, holds if $f$ is a continuous function, which is typically the case in Calculus II problems.

Thus, to find $L$, you solve the fixed-point equation $L=f(L)$. For $a_{n+1}=\frac{1}{2}{a}_n+3$, the equation is $L=\frac{1}{2}L+3$. Solving yields $\frac{1}{2}L=3$, so $L=6$. This matches our inductive bound and confirms the sequence creeps up toward 6.

Connections to Fixed-Point Iteration

The process we've outlined—choosing a starting value, applying $a_{n+1}=f(a_n)$, and analyzing convergence—is precisely the algorithm of fixed-point iteration, a fundamental numerical method. The limit $L$ satisfying $L=f(L)$ is called a fixed point. In engineering contexts, $f(x)$ is often derived from rearranging an equation like $g(x)=0$ into the form $x=f(x)$.

The convergence of fixed-point iteration is not guaranteed. It depends critically on the function $f$ and the initial guess. A key diagnostic tool is the magnitude of the derivative at the fixed point, $|f^{\prime }(L)|$. If $|f^{\prime }(L)|<1$, the iteration will typically converge for starting values near $L$; if $|f^{\prime }(L)|>1$, it will typically diverge. This explains why some recursive schemes work beautifully while others spiral out of control, a vital consideration when designing your own numerical algorithms.

Common Pitfalls

1. Assuming Convergence Without Proof: Never assume a recursive sequence converges just because the first few terms seem to approach a number. You must formally establish boundedness and monotonicity to use the MCT, or use other convergence tests. Sequences like $a_{n+1}=2a_n-1$ with $a_0=1.1$ diverge, even if the first few steps seem stable.
2. Misapplying the Limit Trick: The step of solving $L=f(L)$ to find the limit is only valid if you already know the limit exists. You cannot "assume convergence" by solving for $L$ and then claim the sequence converges to that $L$. The logic must flow: prove convergence (e.g., via MCT) first, then use the limit trick to find its value.
3. Confusing Sequence Types: A recursively defined sequence is fundamentally different from a series. A sequence is an ordered list of numbers $\{a_1,a_2,a_3,...\}$. A series is the sum of a sequence: $a_1+a_2+a_3+...$. The convergence tests and behaviors for each are distinct. Do not apply series tests (like the Integral Test) to a sequence.
4. Overlooking the Need for Induction: Proving a sequence is monotone or bounded often requires a clear proof by induction. A common error is to check the first three terms, observe a pattern, and conclude it holds for all $n$. A proper inductive proof is necessary for mathematical rigor, especially in a high-priority engineering context where algorithm stability is paramount.

Summary

• A recursively defined sequence $a_{n+1}=f(a_n)$ is computed iteratively, modeling the core of many numerical algorithms used in engineering.
• To analyze such a sequence, you must investigate its boundedness (is it contained within finite limits?) and monotonicity (is it consistently increasing or decreasing?).
• The Monotone Convergence Theorem is a powerful guarantee: if a sequence is both bounded and monotone, it must converge to a real limit $L$.
• Once convergence is assured, you can find the limit $L$ by solving the fixed-point equation $L=f(L)$, provided $f$ is continuous.
• This entire process is the theory behind fixed-point iteration methods, where the condition $|f^{\prime }(L)|<1$ often determines whether an iterative numerical scheme will succeed or fail.