Algebra 1 · F.BF.A.1A · F.BF.A.2

Recursive formulas

If you know where a list of numbers starts and how each number turns into the next, is that enough to pin down the whole list?

You need

Geometric sequences and the explicit formulaAlgebra 1

Unlocks

Generating a sequence from a ruleAlgebra 1

Where you are 10 in Sequences and series

Algebra9

Sequences and series10

▴ 5 above Sigma notation Arithmetic series and partial sums Geometric series

Recursive formulas

Infinite geometric series

Why this exists

Many quantities are easiest to describe by how they change from one step to the next. A library adds 40 books every month. A waiting list loses a quarter of its names every week. A jar of sourdough starter doubles overnight, and then 100 grams are taken out to bake with. It may be hard to say at once how much there will be in month 30, but it is easy to say what next month looks like once you know this month.

A recursive formula writes exactly that down. It names where the list starts and how each term turns into the next, and the whole sequence unrolls from there, one step at a time.

You already know sequences and the notation a_n from Sequences, terms and notation, and the explicit formulas for arithmetic and geometric sequences, which give a_n straight from n. A recursive formula describes the same sequences the other way: step by step instead of all at once.

Definition

A recursive formula for a sequence has two parts:

a starting value, the first term given as a number, such as a_1 = 7;
a recursive rule, which says how to get each term from the term before it, such as a_n = a_{n-1} + 4 for n \ge 2.

The symbol a_{n-1} is read “a sub n minus one” and means the term just before a_n. Its position n - 1 is one less than n, so when a_n is the fifth term, a_{n-1} is the fourth. The rule a_n = a_{n-1} + 4 therefore says: each term is the term before it, plus 4. The note “for n \ge 2” is there because the first term has no term before it; it comes from the starting value instead.

Two kinds of rule appear most often. The formula

a_1 = 7, \qquad a_n = a_{n-1} + 4 \quad (n \ge 2)

adds the same number at every step, so it describes an arithmetic sequence with common difference 4: 7, 11, 15, 19, \dots The formula

a_1 = 5, \qquad a_n = 2 \cdot a_{n-1} \quad (n \ge 2)

multiplies by the same number at every step, so it describes a geometric sequence with common ratio 2: 5, 10, 20, 40, \dots

A sequence is a function whose inputs are the positions 1, 2, 3, \dots, so the same formula can be written in Function notation. With f(n) for the term in position n,

f(1) = 7, \qquad f(n) = f(n - 1) + 4 \quad (n \ge 2)

says exactly what the first formula says, with f(n-1) as the term before f(n). Both notations are common and mean the same thing.

Intuition

Picture the sequence as a row of boxes joined by arrows. The starting value fills the first box. The rule is the arrow: it says what to do to the number in one box to fill the next. Follow the arrows and every box gets filled, in order.

Figure 1The shaded box is the starting value; each arrow is the rule. Top, a_1 = 7 and a_n = a_{n-1} + 4. Bottom, a_1 = 5 and a_n = 2 \cdot a_{n-1}.

The arrows alone are not enough. The rule a_n = a_{n-1} + 4 fits 7, 11, 15, 19, \dots, but it fits 2, 6, 10, 14, \dots just as well, and every other starting number gives yet another sequence. All of them climb by the same 4 at each step, so on a graph they make parallel rows of points, one above the other. The rule fixes the shape; the starting value fixes where the shape sits.

Figure 2The same rule, a_n = a_{n-1} + 4, from two starts. The rows climb alike and stay 5 apart.

Results

Arithmetic sequence. With first term a_1 and common difference d, the recursive rule is a_n = a_{n-1} + d for n \ge 2.

Geometric sequence. With first term a_1 and common ratio r, the recursive rule is a_n = r \cdot a_{n-1} for n \ge 2.

One start and one rule give one sequence. A starting value together with a rule that uses only the term before fixes every term. The same rule with a different start gives a different sequence.

Reading a rule off a list. If the differences a_2 - a_1, a_3 - a_2, and so on are all equal to d, the list fits a_n = a_{n-1} + d. If the ratios \displaystyle \frac{a_2}{a_1}, \displaystyle \frac{a_3}{a_2}, and so on are all equal to r, it fits a_n = r \cdot a_{n-1}.

Why it is true

Take the claim that a start and a rule fix every term. The starting value gives a_1. The rule, applied to that one number, gives exactly one value for a_2, because it is a calculation and a calculation has one answer. Applied to a_2 it gives exactly one a_3, and so on. Reaching position n takes n - 1 steps, a finite number, and no step offers a choice, so every term is reached and each has exactly one value.

The start cannot be left out. Suppose two sequences follow the same rule a_n = a_{n-1} + d but begin at numbers that differ by k. Adding d to both keeps the gap, since (a + d) - (b + d) = a - b. The gap k is carried down the whole chain unchanged, which is the constant spacing between the two rows in the graph above, so the two sequences never agree.

The list tests are the rules rearranged. Subtracting a_{n-1} from both sides of a_n = a_{n-1} + d gives a_n - a_{n-1} = d, and dividing both sides of a_n = r \cdot a_{n-1} by a_{n-1} (allowed when a_{n-1} \ne 0) gives \displaystyle \frac{a_n}{a_{n-1}} = r.

Worked examples

Example 1

Terms from an adding rule and a multiplying rule

Write the first five terms of each sequence.

(a) a_1 = 7, a_n = a_{n-1} + 4 for n \ge 2.

(b) a_1 = 5, a_n = 2 \cdot a_{n-1} for n \ge 2.

Solution

(a) The first term is given. Each later term is the one before plus 4, so put n = 2, 3, 4, 5 into the rule in turn, each time using the term just found.

\begin{aligned} a_2 &= a_1 + 4 = 7 + 4 = 11\\ a_3 &= a_2 + 4 = 11 + 4 = 15\\ a_4 &= a_3 + 4 = 15 + 4 = 19\\ a_5 &= a_4 + 4 = 19 + 4 = 23 \end{aligned}

The first five terms are 7, 11, 15, 19, 23.

(b) This time each term is twice the one before.

\begin{aligned} a_2 &= 2 \cdot a_1 = 2 \cdot 5 = 10\\ a_3 &= 2 \cdot a_2 = 2 \cdot 10 = 20\\ a_4 &= 2 \cdot a_3 = 2 \cdot 20 = 40\\ a_5 &= 2 \cdot a_4 = 2 \cdot 40 = 80 \end{aligned}

The first five terms are 5, 10, 20, 40, 80. Neither a_5 nor a_4 could be found without the term before it: a recursive formula is worked forward one term at a time.

Example 2

Same rule, different start

The rule b_n = 3 \cdot b_{n-1} is used with three starting values: b_1 = 2, b_1 = -1 and b_1 = 0. Write the first four terms in each case.

Solution

The rule is the same each time, multiply the term before by 3; only the first box changes.

With b_1 = 2: b_2 = 3 \cdot 2 = 6, b_3 = 3 \cdot 6 = 18, b_4 = 3 \cdot 18 = 54. The terms are 2, 6, 18, 54.

With b_1 = -1: b_2 = 3 \cdot (-1) = -3, b_3 = 3 \cdot (-3) = -9, b_4 = 3 \cdot (-9) = -27. The terms are -1, -3, -9, -27.

With b_1 = 0: every product is 3 \cdot 0 = 0, so the terms are 0, 0, 0, 0.

Three starts, three different sequences: one grows, one falls ever further below zero, one never moves. The rule says how the sequence moves; only the start says where it begins.

Example 3

A library that adds books

At the end of its first month a new library holds 2{,}350 books, and it adds 40 books every month after that. Let L_n be the number of books at the end of month n. Write a recursive formula for L_n, in subscript and in function notation, and find the first month in which the library holds more than 2{,}500 books.

Solution

The starting value is the count at the end of month 1, so L_1 = 2350. Each month’s count is the month before plus 40:

L_1 = 2350, \qquad L_n = L_{n-1} + 40 \quad (n \ge 2).

In function notation, with L(n) for the count at the end of month n, the same formula is L(1) = 2350 and L(n) = L(n-1) + 40 for n \ge 2.

Now run the rule until the count passes 2{,}500.

\begin{aligned} L_2 &= 2350 + 40 = 2390\\ L_3 &= 2390 + 40 = 2430\\ L_4 &= 2430 + 40 = 2470\\ L_5 &= 2470 + 40 = 2510 \end{aligned}

L_4 = 2470 is still below 2{,}500 and L_5 = 2510 is above it, so month 5 is the first.

Example 4

Writing the rule from a list and from a table

(a) Write a recursive formula for 50, 41, 32, 23, \dots

(b) A waiting list is counted at the start of each week.

week n	1	2	3	4
names w_n	256	192	144	108

Write a recursive formula for w_n and use it to predict week 5.

Solution

(a) Subtract each term from the next: 41 - 50 = -9, 32 - 41 = -9, 23 - 32 = -9. Every difference is -9, so each term is the one before minus 9. With the first term as the start,

a_1 = 50, \qquad a_n = a_{n-1} - 9 \quad (n \ge 2).

(b) The differences are 192 - 256 = -64, 144 - 192 = -48 and 108 - 144 = -36. They are not equal, so no adding rule fits. Try ratios instead.

\frac{192}{256} = \frac{3}{4}, \qquad \frac{144}{192} = \frac{3}{4}, \qquad \frac{108}{144} = \frac{3}{4}

Every ratio is \tfrac34, so each week’s list is three quarters of the week before. That matches a list losing a quarter of its names each week, since what remains is 1 - \tfrac14 = \tfrac34 of it. The formula is

w_1 = 256, \qquad w_n = \tfrac34 \cdot w_{n-1} \quad (n \ge 2),

and in week 5 it predicts w_5 = \tfrac34 \cdot 108 = 81 names.

Example 5

Double, then take away 100

A sourdough starter weighs 150 grams on the morning of day 1, just after some has been taken out for baking. Each night it doubles in weight, and each morning 100 grams are taken out. Let s_n be its weight in grams on the morning of day n, after the 100 grams are taken out. Write a recursive formula and find s_5.

Solution

Follow one night and one morning. From s_{n-1} grams the starter doubles overnight to 2 \cdot s_{n-1}, and then 100 grams come out, leaving 2 \cdot s_{n-1} - 100. So

s_1 = 150, \qquad s_n = 2 \cdot s_{n-1} - 100 \quad (n \ge 2).

The rule matches the order of events: multiply first, then subtract, which is also the order the usual order of operations gives. Work forward, doubling and then subtracting each time.

\begin{aligned} s_2 &= 2 \cdot 150 - 100 = 300 - 100 = 200\\ s_3 &= 2 \cdot 200 - 100 = 400 - 100 = 300\\ s_4 &= 2 \cdot 300 - 100 = 600 - 100 = 500\\ s_5 &= 2 \cdot 500 - 100 = 1000 - 100 = 900 \end{aligned}

So s_5 = 900 grams. This sequence is neither arithmetic nor geometric: the differences 50, 100, 200, 400 are not equal, and the ratios \displaystyle \frac{200}{150} = \frac43 and \displaystyle \frac{300}{200} = \frac32 are not equal either. A recursive rule is not limited to the two standard kinds; any rule that turns one term into the next will do.

Example 6

Working backward to the start

Another starter follows the same pattern, f(n) = 2 \cdot f(n-1) - 100, where f(n) is its weight in grams on the morning of day n. On the morning of day 4 it weighs 260 grams. What did it weigh on the morning of day 1?

Solution

The rule links each day to the day before, so it can be read backward. Put n = 4 into the rule:

260 = 2 \cdot f(3) - 100.

Undoing the rule means undoing its steps in reverse order: put the 100 grams back, then halve. Adding 100 to both sides gives 360 = 2 \cdot f(3), and dividing both sides by 2 gives f(3) = 180. The same two moves with n = 3: 180 = 2 \cdot f(2) - 100, so 280 = 2 \cdot f(2) and f(2) = 140. Once more with n = 2: 140 = 2 \cdot f(1) - 100, so 240 = 2 \cdot f(1) and f(1) = 120.

The starter weighed 120 grams on day 1. Check by running the rule forward: 2 \cdot 120 - 100 = 140, then 2 \cdot 140 - 100 = 180, then 2 \cdot 180 - 100 = 260, the weight given for day 4.

Boundaries

A start is required. A rule with no starting value describes a whole family of sequences, one for each possible start, as the second example showed. A rule that reaches back two terms, like the Fibonacci rule in Generating a sequence from a rule, needs two starting values.
The rule begins at n = 2. Applied at n = 1 it would ask for a_0, a term that does not exist in a sequence that starts at position 1.
No skipping. To find a_{50} you need a_{49}, which needs a_{48}, and so on back to the start: 49 uses of the rule. An explicit formula jumps straight to any position; when each kind is the better tool is the subject of Closed form versus recursive form.
A list never proves a rule. A rule read from four terms fits those four; that the pattern carries on is an assumption. The rule must fit every pair shown, not only the first two. A list whose differences and ratios both change, such as 2, 4, 10, 28, fits neither standard kind (it does fit a_n = 3 \cdot a_{n-1} - 2).
The ratio test needs nonzero terms. It divides by a_{n-1}, so it says nothing across a term equal to 0.
A model stops where the setting does. The waiting list rule goes on to w_6 = \tfrac34 \cdot 81 = 60.75 names, which no list can have. The starter rule, from any morning weight below 50 grams, asks to take 100 grams from less than 100 grams and returns a negative weight.

Where this goes next

Rules that reach back two terms, like the Fibonacci rule, are the next step in Generating a sequence from a rule. Closed form versus recursive form turns a recursive formula into an explicit one and back, and weighs when each is better. An adding rule changes by the same amount at every step, the mark of Linear functions, and a multiplying rule changes by the same factor, the mark of Exponential growth and decay. Rules of every kind that build terms from earlier terms are studied as Recurrence relations.

Exercises

Terms from a rule

Each rule holds for n \ge 2.

Write the first five terms: a_1 = 12, a_n = a_{n-1} + 5.
Write the first five terms: a_1 = 40, a_n = a_{n-1} - 7.
Write the first five terms: a_1 = 3, a_n = 5 \cdot a_{n-1}.
Write the first five terms: a_1 = 96, a_n = \tfrac12 \cdot a_{n-1}.
Write the first five terms: a_1 = -3, a_n = -2 \cdot a_{n-1}.
Write the first four terms: f(1) = 4, f(n) = 3 \cdot f(n-1) + 1.

Writing a rule

Write a recursive formula for each sequence.

9, 15, 21, 27, \dots
34, 27, 20, 13, \dots
7, 21, 63, 189, \dots
800, 200, 50, 12.5, \dots
The sequence with f(1) = 4, f(2) = -8, f(3) = 16, f(4) = -32, in function notation.

In context

Jadwiga’s library holds 1{,}180 books at the end of month 1 and adds 40 books each month. Write a recursive formula for B_n, the number of books at the end of month n, and find B_5.
Dunstan’s waiting list has 1{,}024 names in week 1 and loses a quarter of its names each week. Write a recursive formula for w_n, the names in week n, and find w_4.
Estrid’s starter weighs 180 grams on the morning of day 1 and follows s_n = 2 \cdot s_{n-1} - 100. Find s_2, s_3 and s_4.
Blodwen tries the rule s_n = 2 \cdot s_{n-1} - 100 with two starts, (a) s_1 = 100 and (b) s_1 = 90. Write terms of each until something stands out, and say what it means for the starter.

Reasoning

The list 7, 14, 28, 56, \dots begins with the difference 14 - 7 = 7, which suggests a_1 = 7, a_n = a_{n-1} + 7. Test that formula against the list and write a correct one.
Explain why the rule a_n = a_{n-1} + 3 alone does not describe 3, 6, 9, 12, \dots, give a second sequence that also fits the rule, and write a complete formula for 3, 6, 9, 12, \dots
Two rules for a starter: s_n = 2 \cdot s_{n-1} - 100 (double overnight, then take out 100 grams) and t_n = 2 \cdot (t_{n-1} - 100) (take out 100 grams, then double). Start both at 150, find the next two terms of each, and explain why they differ.

Answers

12, 17, 22, 27, 32. Add 5 each time.
40, 33, 26, 19, 12. Subtract 7 each time.
3, 15, 75, 375, 1875. Multiply by 5 each time.
96, 48, 24, 12, 6. Halve each time.
-3, 6, -12, 24, -48. Multiplying by -2 flips the sign at every step: -2 \cdot (-3) = 6, -2 \cdot 6 = -12, and so on.
4, 13, 40, 121. Triple, then add 1: 3 \cdot 4 + 1 = 13, 3 \cdot 13 + 1 = 40, 3 \cdot 40 + 1 = 121.
a_1 = 9, a_n = a_{n-1} + 6 for n \ge 2. Every difference is 6.
a_1 = 34, a_n = a_{n-1} - 7 for n \ge 2. Every difference is -7.
a_1 = 7, a_n = 3 \cdot a_{n-1} for n \ge 2. Every ratio is 3; the differences 14, 42, 126 are not equal.
a_1 = 800, a_n = \tfrac14 \cdot a_{n-1} for n \ge 2. Every ratio is \displaystyle \frac{200}{800} = \frac{50}{200} = \frac{12.5}{50} = \tfrac14.
f(1) = 4, f(n) = -2 \cdot f(n-1) for n \ge 2. Every ratio is -2: \displaystyle \frac{-8}{4} = \frac{16}{-8} = \frac{-32}{16} = -2.
B_1 = 1180, B_n = B_{n-1} + 40 for n \ge 2. The terms run 1180, 1220, 1260, 1300, 1340, so B_5 = 1340.
w_1 = 1024, w_n = \tfrac34 \cdot w_{n-1} for n \ge 2, since losing a quarter leaves three quarters. The terms run 1024, 768, 576, 432, so w_4 = 432.
s_2 = 260, s_3 = 420, s_4 = 740. Doubling then subtracting: 360 - 100, 520 - 100, 840 - 100.
(a) 100, 100, 100, \dots: doubling gives 200 and taking out 100 leaves 100 again, so the weight never changes. (b) 90, 80, 60, 20, and then 2 \cdot 20 - 100 = -60. The starter shrinks each day, and on day 5 only 40 grams are there to take 100 from, so the model breaks down after day 4.
That formula gives 7, 14, 21, 28, which fails at the third term (21, not 28): one difference is not enough to test a rule. The differences 7, 14, 28 change, but every ratio is 2, so the correct formula is a_1 = 7, a_n = 2 \cdot a_{n-1} for n \ge 2.
The rule says only how to step, not where to begin, so any start fits it: a_1 = 1 gives 1, 4, 7, 10, \dots, which also adds 3 each time. The complete formula is a_1 = 3, a_n = a_{n-1} + 3 for n \ge 2.
s gives 150, 200, 300 and t gives 150, 100, 0. Expanding, t_n = 2 \cdot t_{n-1} - 200: taking the 100 grams out before the night means that portion is not there to double, so the night’s growth is 100 grams less than for the first rule.