Sequences and Recurrence Relations

1Introduction

A sequence specifies a term for each natural-number index. An {explicit formula} computes every term directly from its index, whereas a {recurrence relation} determines later terms from known ones. These are two fundamental ways to describe the same mathematical object. This lecture explains their meanings, the role of initial conditions, and their principal examples before directing the reader to the subsequent methods.

2Sequences and Indices

A real sequence $(a_n{)}_{n\ge 1}$(a_n)_{n\geq1} is a function that assigns a real number $a_n$a_n to every integer $n\ge 1$n\geq1. We call $a_n$a_n the $n$nth term and $a_1$a_1 the initial term. Unless stated otherwise, this lecture starts indices at $n=1,2,3,\dots$n=1,2,3,\ldots. Thus, imposing an update equation $a_{n+1}=F(n,a_n)$a_{n+1}=F(n,a_n) “for every $n\ge 1$n\geq1” successively governs $a_2,a_3,\dots$a_2,a_3,\ldots wherever $F$F is defined.

One may instead start indices at $0$0. Under that convention the initial term is $a_0$a_0, and, for example, the formula corresponding to $a_1{r}^{n-1}$a_1r^{n-1} becomes $a_0{r}^n$a_0r^n. Indexing conventions must not be mixed.

3Explicit Formulas and Recurrences

An explicit formula, such as

specifies $a_n$a_n directly from $n$n. By contrast, a recurrence together with an initial condition, such as

specifies relations among the terms and a starting value. Both descriptions give the sequence $3,5,7,\dots$3,5,7,\ldots. An explicit formula is convenient for computing a selected term, while a recurrence naturally expresses change between adjacent terms or a generative process.

4Initial Conditions and Uniqueness

A recurrence alone need not determine a unique sequence. For example,

generates $1,2,4,\dots$1,2,4,\ldots when $a_1=1$a_1=1, but $3,6,12,\dots$3,6,12,\ldots when $a_1=3$a_1=3. The value of $a_1$a_1 is required.

More generally, suppose that

is accompanied by the initial condition $a_1=c\in \mathbb{R}$a_1=c\in\mathbb R, and $F:N_{\ge 1}\times \mathbb{R}\to \mathbb{R}$F:\mathbb N_{\geq1}\times\mathbb R\to\mathbb R assigns one real number to every input. A unique real sequence then exists: $a_1$a_1 determines $a_2=F(1,a_1)$a_2=F(1,a_1), and every term similarly determines the next.

A second-order recurrence that determines $a_{n+2}$a_{n+2} from $a_{n+1}$a_{n+1} and $a_n$a_n usually requires two consecutive initial values. For example,

uniquely generates $1,1,2,3,5,\dots$1,1,2,3,5,\ldots. More generally, let $G:N_{\ge 1}\times R^k\to \mathbb{R}$G:\mathbb N_{\geq1}\times\mathbb R^k\to\mathbb R and consider the order-$k$k recurrence

It uniquely updates the highest-index term from the preceding $k$k terms. Therefore, specifying the $k$k consecutive initial values $a_1,\dots ,a_k$a_1,\ldots,a_k uniquely determines a real sequence.

5Arithmetic and Geometric Sequences

A constant additive change gives an arithmetic sequence. With common difference $d$d,

A constant multiplicative change gives a geometric sequence. With common ratio $r$r,

The former is recognized through the difference $a_{n+1}-a_n$a_{n+1}-a_n and the latter through a common multiplier. When $a_n=0$a_n=0, the quotient $a_{n+1}/a_n$a_{n+1}/a_n is undefined, so geometric behavior must be tested through $a_{n+1}=r{a}_n$a_{n+1}=ra_n without division. The lecture on arithmetic and geometric sequences proves the general-term and finite-sum formulas and handles their exceptional cases.

6A Basic First-Order Recurrence

For constants $p,q$p,q, consider

If $p=1$p=1, then $a_{n+1}=a_n+q$a_{n+1}=a_n+q, so the sequence is arithmetic. If $p\ne 1$p\ne1, the equilibrium point

satisfies $\alpha =p\alpha +q$\alpha=p\alpha+q; that is, $\alpha$\alpha is a {fixed point} of the update map $x\mapsto px+q$x\mapsto px+q. Define $b_n:=a_n-\alpha$b_n:=a_n-\alpha. Then

so the deviation from equilibrium is geometric. Consequently,

The lecture on first-order recurrences gives the detailed derivation, behavior for different values of $p$p, and examples.

7Choosing a Method

• If the difference is constant, use an arithmetic sequence.
• If every update uses the same multiplier, use a geometric sequence.
• For $a_{n+1}=p{a}_n+q$a_{n+1}=pa_n+q, subtract an equilibrium point to obtain geometric form.
• When several preceding terms occur, identify the order and coefficient structure and examine whether methods such as a characteristic equation apply.
• To treat index shifts and differences uniformly, use the shift operator.

The lecture on recurrence types and strategies develops classification and method selection. The lecture on shift operators and recurrences develops the shift operator $E$E and the difference operator $\mathrm{\Delta }=E-I$\Delta=E-I.

8Cautions in Application

Finitely many displayed terms cannot uniquely determine the rule of an infinite sequence: infinitely many sequences can agree on those terms and differ later. Moreover, when a recurrence contains fractions or square roots, one must check that its right-hand side is defined at every stage. Even a formal update rule with initial conditions need not produce all later terms within the specified number system.

9Summary

• A sequence $(a_n{)}_{n\ge 1}$(a_n)_{n\geq1} is a function assigning a term $a_n$a_n to every integer $n\ge 1$n\geq1.
• An explicit formula specifies $a_n$a_n directly from the index; a recurrence specifies later terms from known ones.
• Unique recursive determination requires suitable initial conditions for the order and a uniquely defined value at every update.
• Arithmetic form, geometric form, and an equilibrium shift are the basic tools for first-order recurrences.

10Related Lectures

11Exercises