Algebra 1 · 4.OA.C.5 · 5.OA.B.3

Generating a sequence from a rule

You know how a sequence starts and how each term makes the next. What does the whole sequence look like, and what does it do that the rule never said?

You need

Recursive formulasAlgebra 1

Unlocks

The Fibonacci sequenceDiscrete 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

When you reach for it

A rule such as “double the term and subtract 1” says nothing on its own. It only turns one number into the next. Give it a first term and it produces a whole sequence, one term at a time: from 4 it gives 7, from 7 it gives 13, and so on for as long as you care to go.

You reach for this move whenever a sequence is described by how it grows rather than by where each term sits: a count that builds on the counts before it, a distance logged hour by hour, a game counter whose next square depends on the square it is on. Rules like “add 3” and “multiply by 2” appeared in patterns from a rule and the basics of sequences. Here the rules square, mix two operations, look back two terms, or treat even and odd terms differently.

The second half of the skill is to look at what comes out. A rule often produces features it never states: every term odd, ones digits that cycle, two sequences in a fixed ratio. Spotting a feature is useful; explaining it from the rule is what makes it certain.

The procedure

Starting terms. A rule names the terms it uses. “Double and subtract 1” uses only the term just before, so one starting term settles everything. “Add the two terms before” uses two, so it needs two starting terms: a single 1 has nothing to be added to. The number of starting terms matches how far back the rule looks. Without them the rule makes no sequence; with them it makes exactly one, because each new term is forced by terms already known.

Applying the rule. Write the starting terms, apply the rule to the latest term or terms to get the next one, write it down, and apply the rule again. Each step is allowed because the rule is the definition of the next term: nothing else decides it, and every input it needs has already been found. That is also why you cannot skip ahead: the tenth term needs the ninth, and the ninth needs the eighth.

In words, the first rule above is “next = 2 \times \text{this} - 1”. Recursive formulas write the same thing with notation that names each term by its position; this lesson keeps to words.

Looking for features. Two facts explain most of what you will notice.

Even and odd, and the ones digit, can be followed on their own. Whether a sum or product of whole numbers is even depends only on whether its parts are, and its ones digit depends only on the ones digits of its parts. So for a rule built from adding and multiplying, you can follow just the parity, or just the ones digit, without the full terms.
A repeat repeats forever. If the rule uses only the last term and a term equals an earlier one, everything after it copies what followed the earlier one. For a rule that looks back two terms, the same happens once a pair of neighboring terms repeats. There are only ten ones digits, so under a one-term rule the ones digits followed on their own must repeat, and from then on they cycle.

A feature seen in the listed terms is a guess about the terms not yet listed. It becomes certain only with a reason that covers every step, as Inductive reasoning and Conjecture, and why a pattern is not a proof explain.

Worked examples

Example 1

Double and subtract 1

Start at 4 and apply “double and subtract 1” to write the first six terms. Explain why every term after the first is odd, and find a second pattern hidden in the terms.

Solution

Each term is twice the one before, less 1: 2 \times 4 - 1 = 7, 2 \times 7 - 1 = 13, 2 \times 13 - 1 = 25, 2 \times 25 - 1 = 49 and 2 \times 49 - 1 = 97.

4 \to 7 \to 13 \to 25 \to 49 \to 97

The first six terms are 4, 7, 13, 25, 49, 97.

Twice any whole number is even, and one less than an even number is odd. So whatever goes in, an odd number comes out. The first term is the exception: it is given, not made by the rule, and 4 is even.

Now subtract 1 from each term: 3, 6, 12, 24, 48, 96. These double. The reason is in the rule: if a term is t, the next is 2t - 1, and by the distributive property

(2t - 1) - 1 = 2t - 2 = 2(t - 1)

So “one less than the term” doubles at every step, though the rule never mentions it.

Example 2

Square and add 1, and its ones digits

Start at 0 and apply “square and add 1”. Write the first six terms, then find the ones digit of the 20th term.

Solution

0^2 + 1 = 1, 1^2 + 1 = 2, 2^2 + 1 = 5, 5^2 + 1 = 26 and 26^2 + 1 = 677, so the first six terms are 0, 1, 2, 5, 26, 677. The seventh is 677^2 + 1 = 458330, and after that the terms grow too big to write out.

The ones digit of a square depends only on the ones digit of the number squared, and adding 1 moves the ones digit on by one (9 becoming 0). So follow the ones digits alone:

0 \to 1 \to 2 \to 5 \to 6 \to 7 \to 0

The last step is 7^2 + 1 = 50, which ends in 0. Once the ones digit is back at 0, the rule repeats what it did from the first term, so the ones digits cycle 0, 1, 2, 5, 6, 7 forever, six to a round. The terms ending in 0 are the 1st, 7th, 13th and 19th, and the 20th is one step on: its ones digit is 1.

The terms also alternate even and odd. Squaring keeps a number even or odd, and adding 1 swaps it.

Example 3

A drone’s family tree

A male honeybee, a drone, hatches from an egg that was not fertilized, so he has a mother but no father. A female hatches from a fertilized egg and has both. Trace a drone’s ancestors back generation by generation. How many are there in the 10th generation back, and why does the count follow “add the two before”?

Figure 1Each count is the sum of the two below it. Every bee has a mother, and only the females have a father as well.

Solution

Reading up the figure, the counts are 1 (the drone), 1 (his mother), then 2, 3, 5, 8.

Every bee in a generation has exactly one mother in the next generation back, and each female also has one father there. So

\begin{aligned} \text{next count} = {} &\text{this count} \\ &+ \text{females in this generation} \end{aligned}

The females in a generation are exactly the mothers of the bees one generation nearer the drone, one per bee, so there are as many of them as there were bees in that nearer generation. So the next count is this count plus the one before it, and the rule needs two starting terms: 1 for the drone and 1 for his mother.

Carrying on from 5, 8 gives 13, 21, 34, 55, 89. Counting the drone as generation 0, generation 10 holds 89 ancestors. The same sequence, started 1, 1, is the The Fibonacci sequence.

Example 4

A two-term rule that loops

A sequence starts 5, 8, and after that each term is the term before minus the one before that. Write terms until something repeats, and find the 100th term.

Solution

8 - 5 = 3, 3 - 8 = -5, -5 - 3 = -8, -8 - (-5) = -3, -3 - (-8) = 5 and 5 - (-3) = 8:

5, 8, 3, -5, -8, -3, 5, 8, \dots

The 7th and 8th terms are 5, 8 again. The rule sees only the last two terms, so from this pair on it repeats exactly what it did from the start: the sequence cycles every 6 terms. Since 100 = 6 \times 16 + 4, the 100th term sits where the 4th does in its round: it is -5.

The loop does not depend on the start. From any pair a, b the rule gives b - a, then (b - a) - b = -a, then -a - (b - a) = -b, then -b - (-a) = a - b, then (a - b) - (-b) = a, then a - (a - b) = b. The pair a, b is back after six terms.

Example 5

A hiker and a cyclist, side by side

A hiker and a cyclist leave a trailhead together and log their distances each hour. The hiker covers 4 km each hour and the cyclist 12 km. Pair the logs and compare them. Then compare again when the cyclist starts 10 km along the trail.

Solution

Both rules start at 0: “add 4” and “add 12”.

hour	hiker (km)	cyclist (km)
0	0	0
1	4	12
2	8	24
3	12	36
4	16	48

In every row the cyclist’s distance is 3 times the hiker’s. After any number of hours the hiker’s total is that many 4s and the cyclist’s is the same number of 12s, and each 12 is three 4s. Plotted as pairs (hiker, cyclist), the points lie on a line through (0, 0), the picture of a proportional relationship.

Figure 2With both logs starting at 0, the pairs lie on a line through the origin. Start the cyclist at 10 and the line moves up.

With the cyclist starting at 10, the logs are 10, 22, 34, 46, 58. Now 22 is 5.5 times 4 and 34 is 4.25 times 8: the ratio changes. What stays fixed is that the cyclist is 10 km more than 3 times the hiker, because the logs start that way and each hour adds 12 to the cyclist and 3 \times 4 = 12 to three times the hiker. The points lie on a parallel line that misses (0, 0). A fixed ratio needs both rules to start at 0.

Example 6

A rule that depends on the term

A board game has a track of squares numbered 1, 2, 3, \dots with no end. On an even square the counter moves to the square numbered half as much; on an odd square it moves to three times the number, plus 1. The game ends on square 1. Play it from square 11.

Solution

11 is odd, so the counter goes to 3 \times 11 + 1 = 34. Then 34 is even, so it goes to 17, and so on:

\begin{aligned} &11 \to 34 \to 17 \to 52 \to 26 \to 13 \to 40 \to 20 \\ &\to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1 \end{aligned}

The game ends after 14 moves, having climbed as high as square 52 on the way.

An open question. Does the game end from every starting square? The claim that it always does is the Collatz conjecture, met in Conjecture, and why a pattern is not a proof. Every start anyone has tried reaches 1, and computers have checked an enormous range of them, but no one has proved it. The repeat argument from the procedure gives no help: the track never ends, so nothing forces a square to come round again.

Boundaries

Enough starting terms. A rule that looks back two terms makes nothing from one term.
One output for each input. “Go to some bigger number” does not make a sequence: the next term has to be decided.
The rule must work at every step. “Next = \dfrac{1}{\text{this} - 1}” from 2 gives 1, and then needs \displaystyle \frac{1}{0}, which does not exist. The sequence stops there.
A feature in the listed terms is a guess until a reason covers every step. The parity and ones-digit arguments need a rule built from adding and multiplying whole numbers. Halving breaks them: 12 and 22 both end in 2, but their halves end in 6 and 1.

Where this goes next

Recursive formulas write these rules in notation that names each term by its position. For the simplest rules, adding or multiplying by the same number each time, there is a way to reach any term without the ones before it: the explicit formula for arithmetic sequences and for geometric ones. Closed form versus recursive form weighs the two descriptions. The bee counts lead into the The Fibonacci sequence, and rules that look back two terms are studied fully in Recurrence relations, where some can be solved outright.

Exercises

Build the terms

Start at 3 and apply “triple and subtract 4”. Write the first five terms.
Start at 1 and apply “square and subtract 1”. Write the first six terms.
Start at 10 and apply “halve and add 6”. Write the first five terms, and say what happens to the gap between each term and 12.
A sequence starts 3, 4, and each later term is the sum of the two before. Write the first eight terms.
A sequence starts 1, 2, and each later term is twice the term before plus the one before that. Write the first six terms.

Features the rule does not state

Start at 1 and apply “triple and add 2”. Write the first five terms, explain why every term is odd, and find the ones digit of the 40th term.
The Fibonacci sequence starts 1, 1 and adds the two before. How many of its first 30 terms are even?
Ten squares numbered 0 to 9 form a ring. From square s, a counter moves to the square named by the ones digit of 3s + 1. Starting on square 5, list the squares it visits until it is back on 5. Which squares does it never reach?
On the same ring, where is the counter after 25 moves if it starts on square 0? If it starts on square 2?

Two rules side by side

Sequence A starts at 0 and adds 3; sequence B starts at 0 and adds 6. Write the first five pairs (A, B) and describe how B compares with A.
Sequence A starts at 0 and adds 5; sequence B starts at 0 and adds 2. Write the first six pairs (A, B). How does B compare with A, and where do the points lie when plotted?
A hiker leaves a trailhead and walks 5 km each hour. A cyclist leaves the same trailhead 2 hours later on the same route and rides 15 km each hour. Log both distances hour by hour from the hiker’s start, hours 0 to 5. When does the cyclist draw level, and when is the cyclist ahead?
Sequence A starts at 0 and adds 4; sequence B starts at 1 and adds 8. Is each term of B twice the matching term of A? If not, what is the link?

Reasoning

For “triple and subtract 4”, which starting number gives a sequence that never changes? Show that for any other start, the gap between the term and that number triples at every step.
Explain why “add the two before” needs two starting terms. Show that starting 1, 2 gives the Fibonacci numbers from the second term on.
Explain why the Fibonacci sequence runs odd, odd, even, odd, odd, even, and so on forever.
Sequence A starts at 0 and adds a; sequence B starts at 0 and adds b, where a \ne 0. Explain why every pair (A, B) after the first has B equal to \displaystyle \frac{b}{a} times A, and why that can fail when B starts somewhere else.
Explain why, on the ring of Exercise 8, the counter comes back to its starting square whichever square it starts on.

Answers

3, 5, 11, 29, 83. 3 \times 3 - 4 = 5, 3 \times 5 - 4 = 11, 3 \times 11 - 4 = 29, 3 \times 29 - 4 = 83.
1, 0, -1, 0, -1, 0. 1^2 - 1 = 0, 0^2 - 1 = -1, (-1)^2 - 1 = 0, and from then on it alternates.
10, 11, 11.5, 11.75, 11.875. The gaps below 12 are 2, 1, 0.5, 0.25, 0.125: the gap halves each step, because \displaystyle \left(\frac{t}{2} + 6\right) - 12 = \frac{t - 12}{2}.
3, 4, 7, 11, 18, 29, 47, 76.
1, 2, 5, 12, 29, 70. 2 \times 2 + 1 = 5, 2 \times 5 + 2 = 12, 2 \times 12 + 5 = 29, 2 \times 29 + 12 = 70.
1, 5, 17, 53, 161, and the 40th term ends in 3. Three times an odd number is odd, and odd plus 2 is odd, so from an odd start every term is odd. The ones digits run 1, 5, 7, 3, and then 3 \times 3 + 2 = 11 ends in 1 again, so they cycle in fours. 40 is a multiple of 4, so the 40th term ends like the 4th.
10 of them. The even terms are the 3rd, 6th, 9th and so on (Exercise 16 explains why), and there are 10 multiples of 3 from 3 to 30.
5 \to 6 \to 9 \to 8 \to 5, since 3 \times 5 + 1 = 16, 3 \times 6 + 1 = 19, 3 \times 9 + 1 = 28 and 3 \times 8 + 1 = 25. It never reaches 0, 1, 2, 3, 4 or 7.
From 0: square 1. From 2: square 7. From 0 the loop is 0 \to 1 \to 4 \to 3 \to 0, four moves, and 25 = 4 \times 6 + 1, so the counter ends one move into a round. From 2 the loop is 2 \to 7 \to 2 (as 3 \times 7 + 1 = 22), so after an odd number of moves it is on 7.
(0, 0), (3, 6), (6, 12), (9, 18), (12, 24). Each B term is twice its A term, since each 6 is two 3s.
(0, 0), (5, 2), (10, 4), (15, 6), (20, 8), (25, 10). Each B term is \displaystyle \frac{2}{5} of its A term, and the points lie on a line through (0, 0).
Hiker: 0, 5, 10, 15, 20, 25. Cyclist: 0, 0, 0, 15, 30, 45. Level at hour 3, with 15 km each, and ahead from hour 4 on.
No. The pairs are (0, 1), (4, 9), (8, 17), (12, 25), and each B term is twice the A term plus 1. It starts as 2 \times 0 + 1, and each step adds 8 to B and 2 \times 4 = 8 to twice A, so the extra 1 never changes.
The start 2, since 3 \times 2 - 4 = 2. For a term t, the next term minus 2 is 3t - 4 - 2 = 3(t - 2), three times the old gap. From 3, for instance, the gaps are 1, 3, 9, 27, 81.
The first time the rule is used it adds two numbers, so two must already be there. From 1, 2 the rule gives 3, 5, 8, 13, \dots, which is 1, 1, 2, 3, 5, 8, 13, \dots with the first 1 dropped. Both sequences add the two before and share the pair 1, 2, so they agree from there.
Odd plus odd is even, odd plus even is odd, and even plus odd is odd. From odd, odd the next three terms are even, odd, odd, and the last two are again an odd, odd pair. The rule sees only the last two terms, so the pattern repeats forever.
After any number of steps, A is that many copies of a and B is the same number of copies of b, and each b is \displaystyle \frac{b}{a} times an a. If B starts at some c \ne 0, the first pair is (0, c), and no number times 0 gives c, so no fixed ratio fits even that pair.
The ones digits of 3s + 1 for s = 0, 1, \dots, 9 are 1, 4, 7, 0, 3, 6, 9, 2, 5, 8, all different, so each square is entered from exactly one square. With only ten squares, some square must come round a second time; take the first one that does. If it were not the start, the squares just before its two visits would both lead to it, so they would be the same square, and that square would have repeated earlier. So the first square to repeat is the start.