Discrete Math › Section E · Sequences › Topic E.1
Describing sequences and sums
Many counting questions have a different answer for every size n, and listing those answers in order gives a sequence. This topic sets out the two ways to pin a sequence down, a closed formula and a recursive definition, and the tools for adding up its terms.
One answer for every n
How many ways can you tile a strip 2 units tall and \(n\) units long with dominoes? For lengths 0, 1, 2, 3, 4 the answers are 1, 1, 2, 3, 5. (The empty strip counts as one tiling: place nothing.) Asking the question for every length at once turns one puzzle into an infinite list of numbers, and the list often shows a pattern that a single answer hides. The \(n\)th term might count arrangements, measure an algorithm's running time on an input of size \(n\), or give a balance after \(n\) months.
Notation: terms and indices
A sequence is an ordered list of numbers \(a_0, a_1, a_2, \ldots\), and the whole sequence is written \((a_n)_{n \ge 0}\). The subscripts are called indices, and \(a_n\) is the term with index \(n\). Formally a sequence is a function whose domain is the natural numbers \(\{0, 1, 2, \ldots\}\): \(a_n\) is just the output at input \(n\). Unlike a set, order and repetition matter, so 1, 1, 2 and 2, 1, 1 are different sequences. Discrete mathematics usually starts counting at \(a_0\). The algebra topic "Sequences" started at \(a_1\) instead; write \((a_n)_{n \ge 1}\) when you mean that.
Closed formulas
A closed formula gives \(a_n\) directly from \(n\) using a fixed, finite number of operations. With \(a_n = n^2 + 1\) you find \(a_{10} = 101\) at once, without knowing any earlier term. A warning comes first, though: a handful of opening terms never settles which sequence you have. The list 1, 2, 4, 8, 16 suggests powers of 2, but if you place \(n\) points on a circle, join every pair with a chord and count the regions inside, the counts for \(n = 1\) to 6 run 1, 2, 4, 8, 16, 31. A pattern spotted in data is a guess until it is proved.
Recursive definitions
A recursive definition has two parts: a recurrence relation expressing each term through earlier terms, and initial conditions giving the starting terms. For \(a_n = 3a_{n-1} - 2\) with \(a_0 = 2\), each term is three times the previous one minus 2, so the sequence runs 2, 4, 10, 28, 82. A recurrence that reaches back two steps, like \(a_n = a_{n-1} + a_{n-2}\), needs two initial terms. Recurrences are often easy to read off a problem but slow to evaluate: reaching \(a_{50}\) means climbing through every term before it.
Worked example: computing terms from a recurrence
Find \(a_6\) when \(a_n = a_{n-1} + 2a_{n-2}\) with \(a_0 = 0\) and \(a_1 = 1\). 1. Build upwards from the initial terms: \(a_2 = 1 + 2(0) = 1\). 2. Then \(a_3 = 1 + 2(1) = 3\) and \(a_4 = 3 + 2(1) = 5\). 3. Next \(a_5 = 5 + 2(3) = 11\) and \(a_6 = 11 + 2(5) = 21\). 4. A closed formula that fits is \(a_n = \frac{2^n - (-1)^n}{3}\). Check: at \(n = 6\) it gives \(\frac{64 - 1}{3} = 21\), and at \(n = 3\) it gives \(\frac{8 + 1}{3} = 3\). Where such a formula comes from is the subject of the topic "Exponential sequences and solving recurrences".
Worked example: a recurrence from a description
Let \(t_n\) be the number of domino tilings of the 2 by \(n\) strip. Find a recursive definition. 1. Look at the left end of any tiling. Either one domino stands upright there, or two dominoes lie flat, one above the other. 2. If one stands upright, the rest is a tiling of a 2 by \(n - 1\) strip: \(t_{n-1}\) ways. 3. If two lie flat, they fill the first two columns, and the rest is a 2 by \(n - 2\) strip: \(t_{n-2}\) ways. 4. The two cases never overlap, so \(t_n = t_{n-1} + t_{n-2}\) with \(t_0 = t_1 = 1\), giving 1, 1, 2, 3, 5, 8, 13. These are the Fibonacci numbers shifted by one place.
Sequences worth recognising
A few sequences turn up so often that you should know them on sight. The square numbers 0, 1, 4, 9, 16 have \(a_n = n^2\). The triangular numbers 1, 3, 6, 10, 15 count dots in triangular arrays, with \(T_n = \frac{n(n+1)}{2}\) for \(n \ge 1\). The powers of 2, namely 1, 2, 4, 8, 16, have \(a_n = 2^n\). The Fibonacci numbers 0, 1, 1, 2, 3, 5, 8 are defined by \(F_n = F_{n-1} + F_{n-2}\) with \(F_0 = 0\) and \(F_1 = 1\). Many new sequences are small changes to these, such as \(2^n - 1\).
Partial sums and sigma notation
From any sequence \((a_n)\) you can build its sequence of partial sums, \(b_n = a_0 + a_1 + \cdots + a_n\), the running total. Recursively, \(b_n = b_{n-1} + a_n\). Sigma notation writes the total compactly:
The index \(k\) is a dummy variable, so any letter gives the same value. Sums split and constants factor out, \(\sum (3a_k + c_k) = 3\sum a_k + \sum c_k\), but a sum of products is not the product of sums. Note that sigma notation is not a closed formula: the work still grows with \(n\).
Worked example: counting the steps of a loop
A program compares every pair of items in a list of \(n\) items: item 2 with item 1, item 3 with items 1 and 2, and so on. How many comparisons does it make? 1. Item \(i\) is compared with the \(i - 1\) items before it. 2. The total is
3. That is the triangular number \(T_{n-1} = \frac{(n-1)n}{2}\). For \(n = 5\) it gives 10, matching \(0 + 1 + 2 + 3 + 4\). 4. For large \(n\) the count is about \(\frac{n^2}{2}\), so doubling the list roughly quadruples the work. The topic "Polynomial sequences" proves the triangular formula.
The sequence of differences
The sequence of differences of \((a_n)\) is \(d_n = a_{n+1} - a_n\), how much each term grows to reach the next. For \(a_n = n^2 + n\), the terms 0, 2, 6, 12, 20 have differences 2, 4, 6, 8, and algebra confirms
Going backwards, \(a_{n+1} = a_n + d_n\), so any term is the first term plus a partial sum of the differences: the two operations undo each other. The next topics use differences to decide what kind of closed formula to look for.
Common mistakes to avoid
First, assuming that the first few terms fix the sequence: always prove a guessed formula. Second, mixing up starting indices. If a list begins at \(a_0\), then \(2^n - 1\) and \(2^{n+1} - 1\) describe different sequences, so test your formula on the very first term. Third, giving a recurrence without initial conditions, or with too few for its order. Fourth, miscounting the terms of a sum: \(\sum_{k=2}^{6}\) has 5 terms, not 4 or 6. Fifth, calling sigma notation a closed formula when it still hides a growing pile of additions.
Key takeaways
A sequence is a function on the natural numbers, written \((a_n)_{n \ge 0}\), often starting at index 0. A closed formula computes \(a_n\) directly; a recursive definition gives a recurrence relation plus initial conditions. Recurrences are easy to read off a problem, while closed formulas are fast to evaluate. Partial sums \(\sum_{k=0}^{n} a_k\) form a new sequence with \(b_n = b_{n-1} + a_n\), and the differences \(a_{n+1} - a_n\) undo that process. No finite list of terms proves a pattern.
Flashcards
Flashcard
An ordered list a₀, a₁, a₂, …; formally a function on the natural numbers
Test your understanding
Question 1 of 5
A sequence is defined by aₙ = 2aₙ₋₁ + 3 with a₀ = 1. What is a₃?
Question 2 of 5
Which of these is a closed formula rather than a recursive definition?
Question 3 of 5
What is the value of the sum of (2k − 1) for k = 2 to 5?
Question 4 of 5
Which recursive definition produces 3, 5, 9, 17, 33, … starting from a₀?
Question 5 of 5
What is the sequence of differences dₙ = aₙ₊₁ − aₙ for aₙ = n² + 3n?
