Defining sequences: enumeration, formula, recurrence
Learning Objectives
- State the three common ways to define a sequence: enumeration, closed-form formula, and recurrence.
- Recognise when an enumeration is genuinely ambiguous and a rule is required.
- Compute terms of a sequence from a closed-form formula or from a recurrence with initial conditions.
- Translate a definition between formula and recurrence in simple cases.
Motivation
In the previous lesson we said what a sequence is: a function \(a \colon \mathbb{N} \to \mathbb{R}\). That settles the question of what kind of object we are studying, but it does not yet tell us how to name a particular one. To work with the sequence of powers of two, or of Fibonacci numbers, or of partial sums of \(\tfrac{1}{n^2}\), we need a way to write the sequence down so that another reader can recover every term from what we have given them.
In practice there are three idioms in common use: enumeration, closed-form formula, and recurrence. They are not interchangeable. Each makes different things easy and different things awkward, and one of them is, strictly speaking, not a definition at all.
Enumeration
To define a sequence by enumeration is to list its terms in order, usually with an ellipsis at the end:
\[0,\ 1,\ 4,\ 9,\ 16,\ 25,\ \ldots\]
The reader is expected to recognise a pattern and continue the list. Enumeration is the most informal way to present a sequence; it is convenient for short examples and indispensable for finite sequences, where the listing is itself the sequence.
The limits of enumeration
For an infinite sequence, the "\(\ldots\)" carries all the weight, and it is genuinely ambiguous. The listing \(1,\ 2,\ 4,\ \ldots\) is consistent with \(a_n = 2^n\) (the powers of two: \(1, 2, 4, 8, 16, \ldots\)), but also with "the smallest natural number not yet listed that is not the sum of two earlier listed numbers" (which begins \(1, 2, 4, 8, 11, 16, \ldots\)), and with many other rules. The reader has to guess which the author meant.
To name an infinite sequence unambiguously, the listing is not enough. We need a rule that, given any index \(n\), produces the value \(a_n\) without depending on the reader's intuition.
Closed-form formula
A sequence is given by a closed-form (or explicit) formula when there is an expression \(f(n)\) in the index \(n\) such that
\[a_n = f(n) \quad \text{for every index } n.\]
To compute the \(100\)-th term, substitute \(n = 100\) and evaluate. No earlier terms are needed.
Examples:
\(a_n = n^2\), giving \(0,\ 1,\ 4,\ 9,\ 16,\ 25,\ \ldots\)
\(a_n = \dfrac{1}{n + 1}\), giving \(1,\ \tfrac{1}{2},\ \tfrac{1}{3},\ \tfrac{1}{4},\ \ldots\)
\(a_n = (-1)^n\), giving \(1,\ -1,\ 1,\ -1,\ \ldots\)
Recurrence
A sequence is given by a recurrence when each term is defined in terms of one or more earlier terms, together with initial conditions that fix enough terms for the rule to have something to start from. Both pieces are essential: the same recurrence with different initial conditions produces different sequences.
Examples:
Powers of two. \(a_0 = 1\), and \(a_{n+1} = 2 a_n\) for every \(n \geq 0\). This gives \(1, 2, 4, 8, 16, \ldots\)
Fibonacci. \(F_0 = 0\), \(F_1 = 1\), and \(F_{n+2} = F_n + F_{n+1}\) for every \(n \geq 0\). This needs two initial values, because the rule reaches back two steps. It gives \(0, 1, 1, 2, 3, 5, 8, 13, 21, \ldots\)
The constant 7. \(a_0 = 7\), and \(a_{n+1} = a_n\). A perfectly legitimate, if dull, recurrence.
If we drop the initial condition from the powers-of-two recurrence and only write \(a_{n+1} = 2 a_n\), we have not defined a sequence at all — we have written down a rule that any sequence of the form \(a_n = c \cdot 2^n\) satisfies, for any constant \(c\).
Two presentations of the same sequence
A sequence may have both a closed-form formula and a recurrence. The powers of two are given by the closed form \(a_n = 2^n\) and, equally, by the recurrence \(a_0 = 1,\ a_{n+1} = 2 a_n\). The two presentations refer to the same object; we can verify they agree by computing the first few terms from each.
This is not a coincidence about powers of two. The Fibonacci sequence, defined above by a recurrence, also has a closed-form formula (known as Binet's formula) which we will not derive here. In general, converting between recurrence and closed-form is a non-trivial problem; this is one of the things the technique of mathematical induction — the subject of a later unit — was designed to help with.
Each form makes different things easy. A closed-form formula gives you the \(n\)-th term directly, no matter how large \(n\) is. A recurrence is often the more natural definition (Fibonacci is far easier to state by its recurrence than by Binet's formula) and is usually what one reasons about when proving structural properties of the sequence.
Connection to Computer Science
A closed-form formula corresponds to direct computation: to obtain the answer for input \(n\), you carry out the arithmetic the formula prescribes, and that is all. A recurrence corresponds to step-by-step computation: to obtain the answer for input \(n\), you build up the values for smaller inputs first and combine them. The two styles appear throughout programming, and the same sequence can usually be computed either way; which is preferable depends on what the formula and the recurrence each cost to evaluate.
Does "\(2, 4, 6, 8, \ldots\)" define a sequence?
Almost everyone who reads that listing will continue with \(10, 12, 14, \ldots\) and call it the sequence of even natural numbers. Strictly, however, the listing on its own does not define a single sequence. It is consistent with the rule \(a_n = 2n\) (for \(n \geq 1\)), but also with infinitely many other rules that happen to agree on the first four terms.
What does the work, in everyday mathematical writing, is a shared convention: of all the rules consistent with the listing, the reader picks the simplest. This is an entirely reasonable convention, but it is a convention, not a deduction. As soon as we want to reason precisely about the sequence — to prove, say, that every term is even, or to compute the \(1000\)-th term — the enumeration is no longer enough. We commit to a rule, write it down, and reason from that.
The moral is not that enumeration is wrong. It is that enumeration suggests a sequence; only a formula or a recurrence pins one down.
Exercises
Exercise 1
Let \(a_0 = 1\) and \(a_{n+1} = 3 a_n + 1\) for \(n \geq 0\). Compute the next four terms.
Exercise 2
Starting at \(n = 1\), which closed-form formula gives the sequence \(2, 5, 10, 17, 26, \ldots\)?
Exercise 3
For each of the following, decide whether the sequence is defined by enumeration, a closed-form formula, or a recurrence.
Exercise 4
Let \(F_0 = 0\), \(F_1 = 1\), and \(F_{n+2} = F_n + F_{n+1}\) for \(n \geq 0\). Compute the next four terms.
Summary
There are three common idioms for naming a sequence: enumeration, closed-form formula, and recurrence.
Enumeration lists the terms and trusts the reader to continue the pattern. It is convenient but ambiguous; only a formula or recurrence defines an infinite sequence unambiguously.
A closed-form formula \(a_n = f(n)\) gives the \(n\)-th term directly from the index.
A recurrence gives each term in terms of earlier ones, together with initial conditions sufficient to start the rule.
A sequence may admit several presentations; translating between them is its own problem.