What is a sequence?
Learning Objectives
- Define a sequence formally as a function on the natural numbers.
- Read and write the notation \((a_n)_{n \in \mathbb{N}}\).
- Distinguish sequences from sets.
- Identify finite vs infinite sequences.
Motivation
Many situations in mathematics, science, and computing can be described by listing values in order: the temperature at noon each day, the amount in a savings account each month, the number of operations a program performs as its input grows. In each case, what matters is not just the values but the order in which they appear — the value for "day 1" is different from the value for "day 2," and we want to keep track of which is which.
The mathematical object that captures this idea is the sequence. Once we have it, we can ask precise questions: does the temperature settle to some limit? does the savings grow without bound? does the program slow down at a predictable rate? These questions, and the techniques used to answer them, form a thread that runs from elementary arithmetic to advanced analysis and theoretical computer science.
Sequence
A sequence of real numbers is a function
\[a \colon \mathbb{N} \to \mathbb{R}.\]
The value \(a(n)\) is called the \(n\)-th term of the sequence and is written \(a_n\). The sequence itself is written
\[(a_n)_{n \in \mathbb{N}} \quad \text{or simply} \quad (a_n).\]
More generally, the domain need not be all of \(\mathbb{N}\); it may be \({1, 2, 3, \ldots}\), or any infinite subset of the form \({n_0, n_0+1, n_0+2, \ldots}\). When the domain is clear from context, we just write \((a_n)\) and trust the reader to fill in where the indexing begins.
A function, not just a list
It is tempting to describe a sequence as "an infinite list" and stop there, but the function viewpoint is the one that matters. A sequence assigns, to each natural number \(n\), exactly one value \(a_n\). The same value may appear at many indices (a sequence can be constant: \(a_n = 7\) for every \(n\)), but each index has one and only one value.
This is the same picture you meet in computing: an array of length \(N\) is a function from \({0, 1, \ldots, N-1}\) to the type of its elements; a stream of incoming events is a function from "time step" to "event." Whether the index set is finite or infinite, the rule is the same — give me an index, I give you a value.
Some sequences to keep in mind
The natural numbers themselves: \(a_n = n\), giving \(0, 1, 2, 3, 4, \ldots\)
The reciprocals: \(a_n = \dfrac{1}{n}\) for \(n \geq 1\), giving \(1, \tfrac{1}{2}, \tfrac{1}{3}, \tfrac{1}{4}, \ldots\)
The powers of two: \(a_n = 2^n\), giving \(1, 2, 4, 8, 16, \ldots\)
The alternating signs: \(a_n = (-1)^n\), giving \(1, -1, 1, -1, \ldots\)
The Fibonacci sequence: \(F_0 = 0\), \(F_1 = 1\), and \(F_{n+2} = F_{n+1} + F_n\), giving \(0, 1, 1, 2, 3, 5, 8, 13, \ldots\)
The first four are defined by a single formula in \(n\); the Fibonacci sequence is defined by a rule that tells you how to compute each term from the previous ones. Both styles are perfectly legitimate ways to specify a sequence, and we will return to the distinction in the next lesson.
Order matters; repetition is allowed
A sequence is not the same as a set. The set \({1, 2, 3}\) is identical to \({3, 2, 1}\), but the sequences \((1, 2, 3, 4, \ldots)\) and \((4, 3, 2, 1, \ldots)\) are quite different — and the second one is not really a sequence at all, because the natural numbers go on forever and you cannot start counting backwards from infinity.
Likewise, a sequence may repeat values; a set cannot. The constant sequence \(a_n = 7\) is a legitimate, well-defined object, even though every term equals every other term.
The same distinction appears in computing: a list (or array) preserves order and allows duplicates; a set does neither. Choosing one or the other matters as soon as the question being asked depends on position or multiplicity.
Finite and infinite sequences
Strictly, the definition above gives an infinite sequence, because its domain is \(\mathbb{N}\). For some purposes we also speak of finite sequences, where the domain is restricted to \({1, 2, \ldots, N}\) for some fixed \(N\). A finite sequence is just an ordered list of \(N\) values, written \((a_1, a_2, \ldots, a_N)\).
The interesting questions in this course concern infinite sequences, because that is where new phenomena appear: a sequence can grow without bound, settle to a limit, oscillate, or behave in more subtle ways. None of these have meaningful analogues for a finite sequence of, say, five terms.
A note on indexing
Different sources begin sequences at different indices. Some start at \(n = 0\), others at \(n = 1\). Both conventions are correct; the choice depends on what is being described. The natural numbers are often listed as \(0, 1, 2, \ldots\), so the formula \(a_n = n\) most naturally starts at \(n = 0\). But the reciprocals \(a_n = 1/n\) require \(n \geq 1\), or the first term would be undefined.
In this course we will state the starting index explicitly whenever it is not clear from the formula. When you read a sequence in any text, the first thing to look for is "where does \(n\) begin?" — it will save many confusions later.
The same care appears in computing, where some languages index arrays from \(0\) and others from \(1\). The mathematics does not change, but the bookkeeping does, and getting the convention wrong by one is the origin of an entire class of bugs.
Exercises
Exercise 1
Let \(a_n = n^2 - n\), starting at \(n = 0\). Compute the first five terms.
Exercise 2
Starting at \(n = 1\), which formula gives the sequence \(1, 4, 9, 16, 25, \ldots\)?
Exercise 3
For each of the following, decide whether it is a sequence in the sense of this lesson.
Exercise 4
Starting at \(n = 0\), which formula gives the sequence \(0, 1, 0, 1, \ldots\)?
Summary
A sequence of real numbers is a function \(a \colon \mathbb{N} \to \mathbb{R}\). The value at \(n\) is written \(a_n\) and called the \(n\)-th term.
The whole sequence is written \((a_n)_{n \in \mathbb{N}}\) or \((a_n)\).
A sequence is determined by an assignment: one value for each index. Order is preserved, repetition is allowed.
Sequences may be defined by an explicit formula in \(n\) or by a recurrence — a rule expressing each term in terms of earlier ones.
The same idea — an indexed family of values — appears throughout computing in the form of arrays, streams, and time series.