Lesson · Sequences and Series · Sequences

Sequences and Recursion

A sequence is a function whose inputs are the positive integers, or the first finitely many of them: a first term, a second term, and perhaps a last one. It can be given by a formula for the n-th term, or by starting values and a rule for later ones, and the two forms answer different questions.

Open the interactive lesson Practice

a₁, a₂, a₃, … aₙ is the n-th term; n is an index, not a value explicit aₙ = 5·2ⁿ⁻¹ give it n, it gives you the term recursive a₁ = 5, each term from the one before aₙ = 2aₙ₋₁, n ≥ 2 both parts are required

One sequence, two ways to define it

Core ideas

What this lesson establishes

There is one genuinely new idea here and it is the notation. The object itself is a function, and functions were Lines, Functions and Graphs.

A sequence is a function on integer positions

aₙ is f(n) written differently: hand it 4 and it returns the fourth term. An infinite sequence has domain 1, 2, 3, …; a finite sequence ending at position N has domain 1, 2, …, N. Either graph is a row of separate dots rather than a curve, and one input still gives one output.

Explicit hands you any term; recursive makes you walk

From aₙ = 5·2ⁿ⁻¹ you get a₃₀ in one line. From a₁ = 5, aₙ = 2aₙ₋₁ you get a₃₀ after computing the twenty-nine terms before it. The recursive form is often the one a situation hands you; the explicit form is the one you want.

Where the indexing starts is arbitrary

Some sequences are numbered from a₁ and some from a₀, and both conventions are in use. This course starts at a₁. The trap is a formula written for one convention and read under the other: aₙ = 2ⁿ gives 2, 4, 8, … from n = 1 and 1, 2, 4, … from n = 0.

The material

Sequences, and the two kinds of definition

What the subscript means, what a recursion needs to be complete, and why five terms prove nothing.

Definition · Sequence

A sequence is a function whose domain is the positive integers or a finite initial segment 1, 2, …, N of them. Its outputs are its terms, written a₁, a₂, a₃, …, and aₙ is the n-th term or general term. A sequence that stops is finite; one that does not is infinite.

The subscript is an index, not a multiplication and not a value: a₃ is the third term, whatever number that happens to be. In the sequence 7, 7, 7, … every term is 7 and a₃ = 7; in 10, 20, 30, …, a₃ = 30, not 3.

A sequence is not a set. Order is part of it and repetition is allowed: 1, 0, 1, 0, … has two distinct values and infinitely many terms, and 1, 2, 3 and 3, 2, 1 are different sequences built from the same three numbers.

Example · Three sequences given explicitly

aₙ = 3n - 1 gives 2, 5, 8, 11, 14, … . bₙ = (-1)ⁿ gives -1, 1, -1, 1, … , which is how an alternating sign is usually produced. cₙ = 1/n gives 1, 1/2, 1/3, 1/4, … , whose terms shrink toward 0 without ever reaching it.

Definition · Recursive definition

A recursive definition of a sequence has two parts: one or more initial terms, and a recurrence giving aₙ in terms of earlier terms. Both parts are needed. The recurrence alone does not identify a sequence.

That last sentence is the one to take seriously. The rule aₙ = 2aₙ₋₁ for n ≥ 2 is satisfied by 5, 10, 20, 40, …, by 3, 6, 12, 24, … and by 0, 0, 0, … . It says how to move, not where to start, and a definition missing its initial term is not incomplete in a small way — it names infinitely many different sequences.

Example · The same sequence, both ways

a₁ = 5 with aₙ = 2aₙ₋₁ for n ≥ 2 gives 5, 10, 20, 40, 80, … . So does aₙ = 5·2ⁿ⁻¹, because doubling n - 1 times from 5 is what that formula does. “Geometric Sequences and Series” shows this is the general shape of a geometric sequence.

Example · Two recursions worth knowing

Fibonacci: F₁ = 1, F₂ = 1, Fₙ = Fₙ₋₁ + Fₙ₋₂, giving 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … . It needs two initial terms because the rule reaches back two. Factorial: 0! = 1 and n! = n·(n - 1)!, giving 1, 1, 2, 6, 24, 120, … . “The Binomial Theorem” uses the second one throughout.

From a recursion to a formula, and the check that is not a proof

There is no general method for turning a recursion into an explicit formula. What there is, at this level, is a procedure: compute several terms, look for a pattern, write a candidate formula, and test it on terms you did not use to build it.

Testing is not proving. The sequence 1, 2, 4, 8, 16, … looks settled after five terms, and here is a sequence that starts that way and then does not continue: mark n points on a circle, join every pair by a chord with no three chords meeting at a point, and count the regions the disc is cut into. For n = 1 through 5 the counts are 1, 2, 4, 8, 16. For n = 6 the count is 31.

So a formula that matches the first five terms of a recursion is a candidate, not a fact. Establishing that it matches for every n requires mathematical induction, which this path does not cover: it is the subject of the Induction and Recursion course on the Discrete Mathematics path. Within this course, say "this formula agrees with the first six terms" and mean exactly that.

Interactive

Two definitions of one sequence

A recursive rule and a closed form, generating the list side by side

Two definitions, one list

Enter an explicit formula or a recursion with its initial term, and the lab prints the terms and plots them. Enter both forms of the same sequence and check that the two lists agree term by term.

Worked example

First term a1

Recursive rule for a(n), using p for the previous term

Closed form for a(n), using n

How many terms

——

The recursive rule may use p for the previous term and n for the position: p + 3, p/2 + 1, p + 2n - 1. The closed form uses n alone: n^2, 3*2^(n - 1). Both are evaluated in exact fractions.

Method

Working with a sequence you have been handed

Before any formula, the terms. Writing them out costs a minute and catches an index error at once.

Decide which kind of definition it is

A formula mentioning only n is explicit. A formula mentioning aₙ₋₁ or earlier terms is a recurrence, and it needs initial terms to be a definition at all.

Write out the first four or five terms

Substitute n = 1, 2, 3, 4 and record what comes out. If the sequence was described in words, this is where a misreading shows up while it is still cheap.

Check the recursion has enough initial terms

A rule reaching back one step needs one; a rule reaching back two, like Fibonacci, needs two. Too few and the sequence is not determined; too many and they may contradict the rule.

If you need a distant term, look for a closed form

Guess from the terms, then test the guess on a term you have not used. Report it as a formula that agrees with the terms you checked, unless you can prove more.

Terms and definitions

Score 0 / 0

Choose the answer you can justify.

a₁ = 3, aₙ = 2aₙ₋₁ + 1

The recursion is easy to run and the pattern is visible once the terms are written next to the powers of 2.

a₁ = 3 a₂ = 2(3) + 1 = 7 a₃ = 2(7) + 1 = 15 a₄ = 2(15) + 1 = 31 a₅ = 2(31) + 1 = 63 terms 3 7 15 31 63 one more 4 8 16 32 64 2² 2³ 2⁴ 2⁵ 2⁶ guess aₙ = 2ⁿ⁺¹ - 1 test n = 1: 2² - 1 = 4 - 1 = 3 ✓ n = 4: 2⁵ - 1 = 32 - 1 = 31 ✓ n = 6: 2⁷ - 1 = 128 - 1 = 127, and the recursion gives 2(63) + 1 = 127 ✓

The n = 6 line is the only one doing real work. The first two use terms the guess was built from; the third predicts a term first and then checks it, which is the only kind of test that can fail.

It still is not a proof. What would settle it is the argument that assumes aₖ = 2ᵏ⁺¹ - 1 and shows the recurrence forces aₖ₊₁ = 2(2ᵏ⁺¹ - 1) + 1 = 2ᵏ⁺² - 1, so that the formula, once true anywhere, is true for ever after. That is induction, and it is the Discrete Mathematics path's business rather than this one's.

For a faded conversion, take b₁ = 2 and bₙ = 3bₙ₋₁ + 2 for n ≥ 2. The supplied first move is to compute b₁ + 1 and b₂ + 1 rather than the terms alone. Generate through b₅, propose a closed form, predict b₆, and check that prediction against the recursion. State exactly which positions your check covers before opening the quiz.

Common mistakes

Reading a₃ as a product or as the number 3The subscript names a position. In 10, 20, 30, … the third term is 30 and the index 3 appears nowhere in the answer. The same habit makes aₙ₋₁ look like aₙ - 1, which it is not: it is the previous term, and in 3, 7, 15, 31, … at n = 4 they are 15 and 30.

Off-by-one from an assumed starting indexA formula written for n starting at 1 produces every term one place out when read as though it started at 0. Any answer that is close but shifted by one position is this error, and writing out a₁ explicitly before anything else catches it.

Treating a pattern in the first few terms as settledThe chord-and-regions sequence begins 1, 2, 4, 8, 16 and continues 31. Five agreements are evidence about the sixth term and nothing more, and the honest report says which terms were checked.

Check your understanding

✓

Finish when a recursion without an initial term reads as incomplete, not as terse.

You should be able to run any recursion out to five terms without error, convert between the explicit and recursive forms of a doubling sequence, and state what your explicit formula has actually been checked against.

Note: Two families of sequence have both forms available and a sum that can be written down exactly. “Arithmetic Sequences and Series” takes the ones built by adding a fixed number, “Geometric Sequences and Series” the ones built by multiplying by a fixed number — and the second of those has a surprise in it, which is that infinitely many terms can add up to a finite number.