Algebra 1 · F.BF.A.1A · F.IF.A.3

Closed form versus recursive form

To find the 200th term of a sequence, do you have to work out the 199 terms before it?

You need

Arithmetic sequences and the explicit formulaAlgebra 1

Unlocks

Solving and checking a two-term recurrenceDiscrete Mathematics and Proof

Where you are 6 in Recurrence relations

Logic, proof and discrete math6

Recurrence relations6

Closed form versus recursive form

Generating a sequence from a rule The Fibonacci sequence Setting up a recurrence from a counting problem Solving and checking a two-term recurrence Two-term recurrences with a repeated root

Why this exists

A sequence can be told in two ways. “Start at 4 and add 7 each time” says how to get from one term to the next. “The term in position n is 7n - 3” says how to get any term straight from its position. Both describe the same list, 4, 11, 18, 25, \dots

The first way is how rules usually arrive. A reading challenge says “each day, read 5 more pages than the day before”; a pendulum loses the same fraction of its reach on every swing; a savings plan says “each week, put in 2 dollars more”. Each describes a change from one term to the next.

A step rule has a cost, though. To know the 200th term you need the 199th, and for that the 198th, and so on back to the start: 199 uses of the step. A formula in n answers in one line: 7(200) - 3 = 1397. This lesson is about moving between the two kinds of rule, and about telling when two rules, written differently, describe the same sequence.

Definition

A sequence is a function whose inputs are the counting numbers 1, 2, 3, \dots, and the output for input n is the term a_n (Sequences, terms and notation). There are two common ways to give that function.

A recursive rule gives the first term and a step that makes each term from the one before it (Recursive formulas):

a_1 = 4, \qquad a_n = a_{n-1} + 7 \ \text{ for } n \ge 2

An explicit formula, also called a closed form, gives each term directly from its position n, with no earlier term needed:

a_n = 7n - 3

Two rules describe the same sequence when they give the same term at every position n = 1, 2, 3, \dots, not only at the first few.

Intuition

A recursive rule is like a set of directions: “from where you are, take one more step”. An explicit formula is like an address: “position n is at 7n - 3”. Directions are easy to give and easy to follow one step at a time, but to reach somewhere far away you walk the whole way. An address takes you there at once.

The staircases below show both kinds of rule in one picture. Stage 1 is a landing of 2 blocks with one step of 2 blocks beside it. Each later stage adds one more step of 2 blocks, one block higher than the last.

Figure 1Each stage adds one step of 2 blocks, shaded, to the stage before.

Read stage by stage, the picture says s_1 = 4 and s_n = s_{n-1} + 2: that is the recursive rule. Read as a whole, stage n is the landing of 2 blocks plus n steps of 2 blocks, so s_n = 2n + 2: that is the explicit formula. Counting what was added gives the recursive rule; counting what is there gives the explicit one.

Results

Adding the same number. For an arithmetic sequence with common difference d (Arithmetic sequences and the explicit formula):

\begin{aligned} &a_1 \text{ given}, \quad a_n = a_{n-1} + d \\ &\Longleftrightarrow \quad a_n = a_1 + (n - 1)d \end{aligned}

Multiplying by the same number. For a geometric sequence with common ratio r (Geometric sequences and the explicit formula):

\begin{aligned} &a_1 \text{ given}, \quad a_n = r \, a_{n-1} \\ &\Longleftrightarrow \quad a_n = a_1 r^{\,n-1} \end{aligned}

Going back. From an explicit formula, the first term is the formula at n = 1. The step is the difference a_n - a_{n-1} when that is the same number for every n, or the ratio a_n \div a_{n-1} when that is.

Same sequence. An explicit formula and a recursive rule describe the same sequence when the formula gives the rule’s first term at n = 1 and the formula obeys the rule’s step for every n \ge 2. Agreeing on the first few terms alone is not enough.

Why it is true

The formulas. Start at a_1 and apply the step a_n = a_{n-1} + d again and again: a_2 = a_1 + d, a_3 = a_1 + d + d, a_4 = a_1 + d + d + d. Getting from position 1 to position n takes one step for each move up, which is n - 1 steps, so d has been added n - 1 times and a_n = a_1 + (n - 1)d. Multiplying works the same way: a_n is a_1 multiplied by r exactly n - 1 times, which is a_1 r^{\,n-1}. The exponent is n - 1 and not n because the first term has had no step applied to it.

The same-sequence test. Suppose a formula gives the rule’s first term and obeys the rule’s step. At position 1 the two agree. The recursive rule makes term 2 by applying the step to term 1, and the formula’s term 2 is that same step applied to the same number, so they agree at position 2. The same reasoning carries the agreement from 2 to 3, from 3 to 4, and on up through every position. Without the step check there is nothing to carry the agreement forward, and Example 6 shows two rules that match for three terms and then part.

Worked examples

Example 1

A staircase counted two ways

The staircase pattern in the figure has 4, 6 and 8 blocks in its first three stages. Write a recursive rule and an explicit formula for s_n, the number of blocks in stage n, and find the number of blocks in stage 200.

Solution

Each stage is the stage before with one more step of 2 blocks, so s_1 = 4 and s_n = s_{n-1} + 2.

Every stage keeps the landing of 2 blocks and has n steps of 2 blocks, so s_n = 2n + 2. Check against the figure: s_1 = 4, s_2 = 6, s_3 = 8.

For stage 200 the formula gives s_{200} = 2(200) + 2 = 402 blocks. The recursive rule reaches the same number only by applying the step 199 times, once to get from each stage to the next.

Example 2

From a recursive rule to a formula: adding

A sequence has a_1 = 4 and a_n = a_{n-1} + 7. Write an explicit formula and find a_{50}.

Solution

Each term is 7 more than the one before, so the sequence is arithmetic with d = 7. Then

\begin{aligned} a_n &= 4 + 7(n - 1) \\ &= 4 + 7n - 7 \\ &= 7n - 3 \end{aligned}

where the second line uses the distributive property. Check: the formula gives a_1 = 4, a_2 = 11 and a_3 = 18, the same as 4, 4 + 7 and 11 + 7 from the rule. So a_{50} = 7(50) - 3 = 347.

Example 3

From a recursive rule to a formula: multiplying

Eldric pulls a pendulum aside and lets it go. Its first swing reaches 40 cm from the center, and each swing reaches \displaystyle \frac{4}{5} as far as the one before, so p_1 = 40 and p_n = 0.8 \, p_{n-1}. Write an explicit formula, then find p_5 and p_{20}.

Solution

Each term is the one before multiplied by 0.8, so the sequence is geometric with r = 0.8:

p_n = 40(0.8)^{n-1}

The rule gives p_2 = 32 and p_3 = 25.6, and so does the formula: 40(0.8) = 32 and 40(0.64) = 25.6. Then p_5 = 40(0.8)^4 = 40(0.4096) = 16.384 cm, and

p_{20} = 40(0.8)^{19} \approx 0.58 \text{ cm}

By the recursive rule, p_{20} would take 19 multiplications in a row; the formula takes one power.

Example 4

From a formula to a recursive rule

Write a recursive rule for (a) a_n = 7 - 4n and (b) b_n = 2 \cdot 3^n.

Solution

(a) The first term is a_1 = 7 - 4 = 3. Subtract the term before from the term:

\begin{aligned} a_n - a_{n-1} &= (7 - 4n) - \big(7 - 4(n - 1)\big) \\ &= (7 - 4n) - (11 - 4n) = -4 \end{aligned}

The difference is -4 whatever n is, so a_1 = 3 and a_n = a_{n-1} - 4. The terms run 3, -1, -5, \dots

(b) The first term is b_1 = 2 \cdot 3^1 = 6, not 2, because the exponent here is n and not n - 1. Divide the term by the term before:

\frac{b_n}{b_{n-1}} = \frac{2 \cdot 3^n}{2 \cdot 3^{n-1}} = 3

So b_1 = 6 and b_n = 3b_{n-1}. Check: the rule gives 6, 18, 54 and the formula gives b_3 = 2 \cdot 27 = 54.

Example 5

When the step rule is the natural one

Drusilla’s reading challenge: she reads 12 pages on day 1, and each day she reads 5 more pages than the day before. Write the rule as the challenge states it, then an explicit formula, and find the first day on which she reads at least 100 pages.

Solution

The challenge is stated as a change from one day to the next, so the rule as given is recursive: r_1 = 12 and r_n = r_{n-1} + 5. That is the natural way to say it, and the way to check it day by day.

It is arithmetic with d = 5, so r_n = 12 + 5(n - 1) = 5n + 7. Now the question becomes an inequality:

\begin{aligned} 5n + 7 &\ge 100 \\ 5n &\ge 93 \\ n &\ge 18.6 \end{aligned}

Days are counted in whole numbers, so the first such day is day 19. Check: r_{19} = 102 and r_{18} = 97. The recursive rule alone could find this only by listing terms until one passed 100; the formula turns the question into an inequality.

Example 6

Three rules that start alike

Bryony writes a_n = 2^{n-1}. Hartmut writes h_1 = 1, h_n = 2h_{n-1}. Jerzy writes j_1 = 1, j_n = j_{n-1} + (n - 1). All three give 1, 2, 4 as the first three terms. Which of them describe the same sequence?

Solution

Bryony and Hartmut: the formula gives a_1 = 2^0 = 1 = h_1, and

\frac{a_n}{a_{n-1}} = \frac{2^{n-1}}{2^{n-2}} = 2

for every n \ge 2, which is Hartmut’s step. Both checks pass, so these two are the same sequence at every position.

Jerzy’s rule adds 1, then 2, then 3: j_2 = 1 + 1 = 2, j_3 = 2 + 2 = 4, but j_4 = 4 + 3 = 7, while a_4 = 8. So Jerzy’s rule is a different sequence, 1, 2, 4, 7, 11, \dots, even though it matches the first three terms. Bryony’s steps are 1, 2, 4, 8, \dots and Jerzy’s are 1, 2, 3, 4, \dots; they agree only for the first two steps.

Boundaries

The conversions here work for two kinds of step: adding the same number, and multiplying by the same number. A rule that does both, such as a_n = 2a_{n-1} + 3, also has a closed form, but finding it needs a later method.
Some rules use more than one earlier term. The rule of the The Fibonacci sequence, F_n = F_{n-1} + F_{n-2}, needs the two terms before and two starting terms. A closed formula for it does exist, but it is far beyond this course; the recursive rule is the one to use here.
A step with no starting term fixes no sequence. The rule a_n = a_{n-1} + 7 alone fits 4, 11, 18, \dots and 1, 8, 15, \dots and every other list that climbs by 7.
Positions are counting numbers. The formula 7n - 3 gives a number at n = 0 or n = 2.5, but neither is a term. Some books start counting at a_0; then the arithmetic formula reads a_n = a_0 + nd.
Finding a ratio by dividing a_n \div a_{n-1} needs the terms to be non-zero.

Where this goes next

Generating terms from a rule, any rule, is the work of Generating a sequence from a rule, which also meets the Fibonacci sequence. Rules like Fibonacci’s, where each term uses the two before it, belong to Recurrence relations, and Solving and checking a two-term recurrence shows how to find their closed formulas: guess that the terms are powers, and the rule becomes a quadratic equation. The explicit formula of an arithmetic sequence is a linear function and that of a geometric sequence is an exponential function, each with its inputs limited to the counting numbers, which is how sequences join the study of functions.

Exercises

Recursive rule to explicit formula

a_1 = 4, a_n = a_{n-1} + 6. Write an explicit formula and find a_{40}.
a_1 = 20, a_n = a_{n-1} - 3. Write an explicit formula and find a_{15}.
a_1 = 7, a_n = 2a_{n-1}. Write an explicit formula and find a_{10}.
a_1 = 64, \displaystyle a_n = \frac{1}{4}a_{n-1}. Write an explicit formula and find a_5.
a_1 = -2, \displaystyle a_n = a_{n-1} + \frac{1}{2}. Write an explicit formula and find a_{21}.

Explicit formula to recursive rule

a_n = 4n + 9
a_n = 10 - 2n
a_n = 4 \cdot 5^{n-1}
a_n = 3 \cdot 2^n

In context

Fridtjof’s staircase pattern uses 7 blocks in stage 1, and each stage adds 3 blocks. Write a recursive rule and an explicit formula, find the blocks in stage 50, and find which stage uses exactly 100 blocks.
A pendulum’s first swing reaches 50 cm from the center, and each swing reaches \displaystyle \frac{9}{10} as far as the one before. Write a recursive rule and an explicit formula, find the reach of the 4th swing, and find the first swing that reaches less than half as far as the first.
Jerzy reads 8 pages on day 1 of a reading challenge, and each day 3 more pages than the day before. Write a recursive rule and an explicit formula, and find the pages he reads on day 21.
a_1 = 1000, a_n = a_{n-1} - 7. Write an explicit formula and find the first negative term and its position.

Same sequence or not?

Do a_n = 5n - 1 and b_1 = 4, b_n = b_{n-1} + 5 describe the same sequence?
Do a_n = 2n + 3 and b_1 = 5, b_n = b_{n-1} + 3 describe the same sequence?
Do \displaystyle a_n = 162\left(\frac{1}{3}\right)^n and b_1 = 54, \displaystyle b_n = \frac{1}{3}b_{n-1} describe the same sequence?

Explaining

Drusilla says that to find a_{1000} for a_1 = 4, a_n = a_{n-1} + 7, she must first find a_{999}. Explain why this is true of the recursive rule, say how many times the step is used to reach a_{1000}, and say what the formula a_n = 7n - 3 does instead.
Take a_n = n and b_n = n + (n-1)(n-2)(n-3)(n-4)(n-5). Check that their first five terms agree, find both 6th terms, and explain why five matching terms do not make two rules the same sequence.

Answers

a_n = 4 + 6(n - 1) = 6n - 2, so a_{40} = 238.
a_n = 20 - 3(n - 1) = 23 - 3n, so a_{15} = 23 - 45 = -22.
a_n = 7 \cdot 2^{n-1}, so a_{10} = 7 \cdot 512 = 3584.
\displaystyle a_n = 64\left(\frac{1}{4}\right)^{n-1}, so \displaystyle a_5 = \frac{64}{256} = \frac{1}{4}.
\displaystyle a_n = -2 + \frac{1}{2}(n - 1) = \frac{n - 5}{2}, so \displaystyle a_{21} = \frac{16}{2} = 8.
a_1 = 13, a_n = a_{n-1} + 4. The difference is (4n + 9) - (4(n - 1) + 9) = 4.
a_1 = 8, a_n = a_{n-1} - 2. The difference is (10 - 2n) - (10 - 2(n - 1)) = -2.
a_1 = 4, a_n = 5a_{n-1}. The ratio of 4 \cdot 5^{n-1} to 4 \cdot 5^{n-2} is 5.
a_1 = 6, a_n = 2a_{n-1}. The first term is 3 \cdot 2^1 = 6, not 3, and the ratio is 2.
f_1 = 7, f_n = f_{n-1} + 3; f_n = 7 + 3(n - 1) = 3n + 4. Stage 50 uses 3(50) + 4 = 154 blocks. From 3n + 4 = 100, n = 32: stage 32.
p_1 = 50, p_n = 0.9 \, p_{n-1}; p_n = 50(0.9)^{n-1}. The 4th swing reaches 50(0.729) = 36.45 cm. Half of 50 is 25; p_7 = 50(0.9)^6 \approx 26.57 and p_8 = 50(0.9)^7 \approx 23.91, so the 8th swing is the first.
r_1 = 8, r_n = r_{n-1} + 3; r_n = 8 + 3(n - 1) = 3n + 5. Day 21: 3(21) + 5 = 68 pages.
a_n = 1000 - 7(n - 1) = 1007 - 7n. From 1007 - 7n < 0, \displaystyle n > \frac{1007}{7} \approx 143.9, so the first negative term is a_{144} = 1007 - 1008 = -1. Check: a_{143} = 6.
Yes. a_1 = 5(1) - 1 = 4 = b_1, and (5n - 1) - (5(n - 1) - 1) = 5, the rule’s step.
No. The first terms match, 2(1) + 3 = 5, but the formula’s step is 2, not 3: a_2 = 7 while b_2 = 8.
Yes. \displaystyle a_1 = 162 \cdot \frac{1}{3} = 54 = b_1, and each term of a_n is \displaystyle \frac{1}{3} of the one before, the rule’s step.
The rule defines a_{1000} as a_{999} + 7, so without a_{999} there is nothing to add 7 to, and the same holds all the way down to a_1. Reaching a_{1000} uses the step 999 times. The formula needs no earlier term: a_{1000} = 7(1000) - 3 = 6997.
For n = 1 to 5 one of the factors (n - 1), \dots, (n - 5) is zero, so b_n = n = a_n. At n = 6, a_6 = 6 but b_6 = 6 + 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 126. Five matching terms say nothing about the sixth. Two rules are the same sequence only when they agree at every n, which needs a reason that covers every n, such as a matching first term and a matching step, not a list of cases.