Chapter 8 — Predicting What Comes Next: Exploring Sequences and Progressions

A sequence is a list of numbers written in a definite order, where each number is called a term. The order matters: 2, 4, 6, 8 is a different sequence from 8, 6, 4, 2. We write the terms as a₁, a₂, a₃, … where a₁ is the first term, a₂ is the second, and aₙ is the n^th term. The small number below the letter is called the position or index of the term.

Sequences appear everywhere. The days of the week numbered 1 to 7, the page numbers of a book, the amount in a savings box after each week, and the number of seats in each row of a stadium are all sequences. Here are some examples:

• 2, 4, 6, 8, 10, … (the even numbers)
• 1, 4, 9, 16, 25, … (the square numbers)
• 1, 1, 2, 3, 5, 8, 13, … (each term after the first two is the sum of the two terms before it; this is the Fibonacci sequence)
• 5, 5, 5, 5, … (a constant sequence)
• 100, 50, 25, 12.5, … (each term is half of the one before)

A sequence can be finite, with a last term, such as the marks of ten students in a test. It can also be infinite, going on without end, such as the counting numbers 1, 2, 3, … where the three dots show that the pattern continues.

A sequence need not follow a pattern that anyone can see, such as the daily temperatures in a city. In this chapter we study sequences that do follow a pattern, because then we can predict terms we have not yet seen. To find the pattern, ask: how does each term compare with the one before it? Does it increase by the same amount? Does it get multiplied by the same number? Do the numbers match something we know, such as squares?

Finding a pattern. Look at 3, 7, 11, 15, … The differences are 7 − 3 = 4, 11 − 7 = 4 and 15 − 11 = 4. The difference is always 4, so the next terms are 19, 23, 27. Now look at 2, 6, 18, 54, … The differences are 4, 12 and 36, which are not constant. But the ratios are 6 ÷ 2 = 3, 18 ÷ 6 = 3 and 54 ÷ 18 = 3. The ratio is always 3, so the next term is 162.

These two kinds of pattern, a constant difference and a constant ratio, give the two most important sequences in this chapter, the arithmetic progression and the geometric progression. Before we meet them, we need a way of describing the rule of a sequence exactly, which is the subject of the next topic.

To describe a sequence exactly, we give a rule that tells us every term. There are two ways of doing it.

The explicit (or general) rule gives the n^th term directly in terms of n. For the even numbers 2, 4, 6, 8, …, the n^th term is aₙ = 2n. Put n = 1 and we get 2, put n = 5 and we get 10, and put n = 100 and we get 200 at once, without writing any of the terms in between. For the square numbers, aₙ = n². For the sequence 4, 7, 10, 13, …, the rule is aₙ = 3n + 1, because 3(1) + 1 = 4, 3(2) + 1 = 7, and so on.

The recursive rule gives the first term and a rule for finding each term from the one before. For 4, 7, 10, 13, …, we write a₁ = 4 and aₙ₊₁ = aₙ + 3. It means: start at 4, and to get any term, add 3 to the previous one. For the doubling sequence 3, 6, 12, 24, …, the recursive rule is a₁ = 3 and aₙ₊₁ = 2aₙ. The Fibonacci sequence is naturally recursive: F₁ = 1, F₂ = 1 and Fₙ₊₁ = Fₙ + Fₙ₋₁.

Each rule has its advantages. The explicit rule is quick when you want a faraway term. To find the 50th term of aₙ = 3n + 1 you just compute 3(50) + 1 = 151. The recursive rule is often easier to see from a picture or a story, because it says what happens at each step, but to find the 50th term you would need all 49 terms before it.

Turning one into the other. From the recursive rule a₁ = 4, aₙ₊₁ = aₙ + 3, we see that we add 3 each time, so a₂ = 4 + 3, a₃ = 4 + 3 + 3, and a₍ₙ₎ = 4 + 3(n − 1) = 3n + 1, which is the explicit rule. The two descriptions are the same sequence.

Checking a rule. Always test a proposed rule on the first few terms. If someone claims that aₙ = 2n + 1 describes 3, 5, 7, 9, …, we test: 2(1) + 1 = 3, 2(2) + 1 = 5, 2(3) + 1 = 7, 2(4) + 1 = 9. It works. A rule that fails even once is wrong.

In everyday life, computer programs often describe a sequence by a recursive rule, because it is simple to repeat the same step. Learning to write both rules prepares you for thinking step by step, which is the basis of algorithms.

An arithmetic progression, or AP, is a sequence in which each term is obtained by adding the same fixed number to the previous term. That fixed number is called the common difference, written d. The first term is written a. So an AP looks like a, a + d, a + 2d, a + 3d, …

To check whether a sequence is an AP, subtract each term from the next. If all the differences are equal, it is an AP. For 7, 10, 13, 16, … the differences are 3, 3, 3, so a = 7 and d = 3. For 20, 17, 14, 11, … the common difference is −3, and the AP is decreasing. For 5, 5, 5, 5, … the common difference is 0, and the AP is constant. In 1, 2, 4, 7, … the differences are 1, 2, 3, which are not equal, so it is not an AP.

The n^th term. Look at how the terms are built:

The n^th term is found by adding the common difference (n − 1) times to the first term. This is the formula of the AP:

aₙ = a + (n − 1)d

Using the formula. For the AP 7, 10, 13, … the 20^th term is a₂₀ = 7 + (20 − 1) × 3 = 7 + 57 = 64. For the AP 20, 17, 14, … the 10^th term is 20 + 9 × (−3) = 20 − 27 = −7.

Which term is a given number? To find out whether 301 is a term of the AP 5, 8, 11, … we set 5 + (n − 1) × 3 = 301. Then 3(n − 1) = 296, and n − 1 = 98.67, which is not a whole number, so 301 is not a term. A term number must be a positive whole number. But for the number 302 we get 3(n − 1) = 297 and n = 100, so 302 is the 100^th term.

Every AP has a straight-line pattern, which we draw in the next topic. For now, remember that for an AP it is the difference that is constant, not the ratio.

A graph can show the pattern of a sequence. To draw the graph of a sequence, plot the points (n, aₙ), with the term number n on the horizontal axis and the term aₙ on the vertical axis. Do not join the points, because n can only be a whole number.

Take the AP 3, 5, 7, 9, 11. Its points are (1, 3), (2, 5), (3, 7), (4, 9) and (5, 11). If you plot them, you will see that they all lie on one straight line. This is true for every AP. The reason is that each time n goes up by 1, aₙ goes up by exactly d, so the points rise by the same amount each step.

The common difference d tells us how steeply the points rise. A bigger d means a steeper climb. When d is positive, the points rise as you go right; when d is negative, they fall; and when d = 0, they lie on a horizontal line. This is the link between an AP and a linear expression: aₙ = a + (n − 1)d = dn + (a − d), which has the same shape as the linear polynomial you have met.

Many real situations produce an AP:

• A taxi fare. The fare is ₹50 for the first kilometre and ₹12 for each extra kilometre. The fares for 1, 2, 3, … km are 50, 62, 74, …, an AP with a = 50 and d = 12. The fare for 10 km is 50 + 9 × 12 = ₹158.
• Saving money. A child puts ₹20 in a box in the first week and ₹5 more each week than the week before: 20, 25, 30, … The fifteenth week’s deposit is 20 + 14 × 5 = ₹90.
• Seats in a hall. The first row has 18 seats and each row has 2 seats more than the row in front: 18, 20, 22, … The 12^th row has 18 + 11 × 2 = 40 seats.
• A staircase. Each step is 15 cm higher than the one before, so the heights above the floor form an AP with d = 15 cm.

Reading from a graph. If the points of a sequence lie on a straight line, the sequence is an AP. You can find d by counting how much the line rises for one step to the right, and you can find any term by reading off the graph or using the formula.

Modelling with an AP is a useful idea. You decide that a quantity grows by a fixed amount at each step, you identify a and d, and then you can predict a future value or test a plan, such as how many weeks of saving will be needed to reach a target.

A famous story says that a schoolboy named Carl Friedrich Gauss was asked to add the numbers from 1 to 100 and finished within moments. He noticed that the numbers could be paired up from the two ends. The first and last make 1 + 100 = 101. The second and the second last make 2 + 99 = 101. The third and the third last make 3 + 98 = 101. Every such pair adds to 101, and there are 50 pairs, so the total is 50 × 101 = 5050.

This idea gives a formula for the sum of the first n natural numbers 1 + 2 + 3 + … + n. Write the sum twice, once forwards and once backwards, and add:

Each column adds to n + 1, and there are n columns, so 2S = n(n + 1). Dividing by 2:

1 + 2 + 3 + … + n = n(n + 1) ÷ 2

Checking the formula. For n = 4, 1 + 2 + 3 + 4 = 10, and the formula gives 4 × 5 ÷ 2 = 10. For n = 100, we get 100 × 101 ÷ 2 = 5050, the same as Gauss found.

A picture. Arrange dots in a staircase: one dot in the first row, two in the second, and so on up to n dots in the last row. Two such staircases fit together to form a rectangle of n rows and (n + 1) columns, which holds n(n + 1) dots. So one staircase holds half of that, n(n + 1) ÷ 2. This is why the numbers 1, 3, 6, 10, 15, … are called triangular numbers.

Using the formula. To add the numbers from 21 to 50, find the sum up to 50 and take away the sum up to 20: 50 × 51 ÷ 2 − 20 × 21 ÷ 2 = 1275 − 210 = 1065. A handshake problem is another use. If 10 people each shake hands once with every other person, the number of handshakes is 9 + 8 + … + 1 = 9 × 10 ÷ 2 = 45.

The sum of the first n natural numbers is also the sum of an AP with a = 1 and d = 1. Later you will meet a formula for the sum of any AP. For now, the trick of pairing the ends is the key idea, and it is worth remembering.

A geometric progression, or GP, is a sequence in which each term is obtained by multiplying the previous term by the same fixed number. That number is called the common ratio, written r. If the first term is a, the GP is a, ar, ar², ar³, …

To test whether a sequence is a GP, divide each term by the one before it. If all the ratios are equal, it is a GP. For 2, 6, 18, 54, … the ratios are 3, 3, 3, so a = 2 and r = 3. For 80, 40, 20, 10, … the ratio is 1/2 each time, so r = 1/2 and the terms shrink. For 3, −6, 12, −24, … the ratio is −2, and the terms alternate in sign. A sequence like 1, 2, 4, 7, … is not a GP, because the ratios are 2, 2 and 7/4.

The n^th term. Building the terms:

The first term is multiplied by r a total of (n − 1) times to reach the n^th term, so:

aₙ = a × rⁿ⁻¹

Using the formula. For 2, 6, 18, … the 6^th term is a₆ = 2 × 3⁵ = 2 × 243 = 486. For 80, 40, 20, … the 5^th term is 80 × (1/2)⁴ = 80 × 1/16 = 5. For 3, −6, 12, … the 4^th term is 3 × (−2)³ = 3 × (−8) = −24.

Compare with an AP. In an AP the same number is added each time and the n^th term has (n − 1) copies of d. In a GP the same number is multiplied each time and the n^th term has the ratio raised to the power (n − 1). A GP with a ratio larger than 1 grows much faster than an AP.

A caution. The common ratio can be a fraction, which makes the terms shrink, or negative, which makes them alternate. But it cannot be zero, because a GP of that kind would have all terms equal to zero after the first one, which is not a useful pattern.

When we plot the points (n, aₙ) of a GP, they do not lie on a straight line. If r is greater than 1, the points curve upwards more and more steeply. If r is between 0 and 1, the points fall quickly at first and then flatten out, getting closer and closer to the horizontal axis without reaching it. This curved shape is the mark of a GP, just as a straight line is the mark of an AP.

Compare the AP 2, 4, 6, 8, 10, 12 with the GP 2, 4, 8, 16, 32, 64. The first six terms start equally, but by the sixth term the AP has reached 12 while the GP has reached 64. A quantity that doubles each step soon becomes huge. This is why GP growth surprises people.

Many situations are modelled by a GP:

• Paper folding. Each fold doubles the number of layers: 1, 2, 4, 8, 16, … After 10 folds there would be 2¹⁰ = 1024 layers, which is why real paper cannot be folded this often.
• Bacteria. A bacterium divides into two every hour. Starting with 1, the numbers are 1, 2, 4, 8, … and after 10 hours there are 2¹⁰ = 1024 bacteria. With a starting number of 5, the count after 6 hours is 5 × 2⁶ = 320.
• A bouncing ball. A ball dropped from 64 cm rebounds to half its previous height each time: 64, 32, 16, 8, … The rebound height after 4 bounces is 64 × (1/2)⁴ = 4 cm.
• Spreading news. If every person who hears a message tells 3 new people, the numbers who hear it at each stage are 1, 3, 9, 27, … a GP with r = 3.
• Falling value. A machine loses 10% of its value each year, so its value is multiplied by 0.9 each year. If it costs ₹10 000, its value after 3 years is 10 000 × 0.9³ = ₹7 290.

A GP with r greater than 1 is called exponential growth, and with r between 0 and 1 it is exponential decay. Many natural and economic processes follow these patterns, from a spreading infection to the cooling of tea.

How to choose between the models. Compare the sequence’s growth. If it adds the same amount each step, use an AP. If it multiplies by the same factor each step, use a GP. Always test the first few terms before choosing.

A fractal is a shape that shows the same pattern again and again at smaller and smaller scales: when you zoom into a part of it, you see a smaller copy of the whole. Fractals appear in nature, in the branches of a tree, a fern leaf, the coastline of a country, and in the structure of a cauliflower. They can be built by repeating a simple rule, and the numbers that describe each stage often form a geometric progression.

The Sierpinski triangle. Start with a solid triangle of area 1. In each step, join the midpoints of the sides of every solid triangle and remove the middle one. The number of solid triangles after each step is:

The number of triangles forms a GP with ratio 3, because each triangle is replaced by 3 smaller ones. The solid area forms a GP with ratio 3/4, because each step keeps three of the four equal pieces. As the steps continue, the area gets closer and closer to zero, even though there are more and more triangles. After 5 steps there are 3⁵ = 243 triangles and the area left is (3/4)⁵ = 243/1024, about 0.24.

The Koch snowflake. Start with an equilateral triangle whose side is 1 unit, so the perimeter is 3. In each step, divide every side into three equal parts and put a small equilateral bump on the middle part. Each side becomes 4 pieces, each one-third of the old length, so the perimeter is multiplied by 4/3 in every step. The perimeters are 3, 4, 16/3, 64/9, … a GP with ratio 4/3. The perimeter keeps growing without limit, although the shape always fits inside a circle.

Why is this interesting? In fractals, the number of pieces and the size of each piece change in a geometric way: one grows by a fixed factor and the other shrinks by a fixed factor. A GP is therefore the natural mathematical tool to describe them.

Try it yourself. Draw the first two steps of the Sierpinski triangle on paper by joining midpoints. Count the solid triangles and check them against 3ⁿ. Then compute the remaining area as a fraction. Doing the drawing once makes the numbers meaningful.

The Tower of Hanoi is a puzzle with three pegs and a stack of discs of different sizes on the first peg, with the largest at the bottom and the smallest on top. The aim is to move the whole stack to another peg, following two rules: only one disc may be moved at a time, and a larger disc may never be placed on a smaller disc.

Let us find the smallest number of moves needed. Write T(n) for the number of moves needed for n discs.

• 1 disc: one move. T(1) = 1.
• 2 discs: move the small disc to the spare peg, move the large disc to the target, then move the small disc on top. That is 3 moves. T(2) = 3.
• 3 discs: first move the top 2 discs to the spare peg (3 moves), then move the largest disc to the target (1 move), then move the 2 discs onto it (3 moves). That is 3 + 1 + 3 = 7 moves. T(3) = 7.

The same plan works for any number of discs. To move n discs, first move the top (n − 1) discs out of the way, which takes T(n − 1) moves. Then move the biggest disc, which takes 1 move. Then move the (n − 1) discs back on top, which takes T(n − 1) moves again. This gives a recursive rule:

T(n) = 2 × T(n − 1) + 1, with T(1) = 1

Using it: T(1) = 1, T(2) = 3, T(3) = 7, T(4) = 15, T(5) = 31. Look at the pattern: each number is one less than a power of 2, namely 2¹ − 1, 2² − 1, 2³ − 1, 2⁴ − 1, 2⁵ − 1. So the explicit rule is:

T(n) = 2ⁿ − 1

The reason is connected with a GP. If you keep substituting, T(n) = 1 + 2 + 4 + … + 2ⁿ⁻¹, which is a sum of the terms of a GP with ratio 2, and this sum is 2ⁿ − 1.

How big does it get? For 10 discs the minimum number of moves is 2¹⁰ − 1 = 1023. For 20 discs it is 2²⁰ − 1 = 1 048 575, more than a million. If a move takes one second, 20 discs need over 12 days. The legend of the puzzle says that monks move 64 golden discs, which would need 2⁶⁴ − 1 moves, a number so large that it would take many times the age of the universe.

The Tower of Hanoi is a good example of computational thinking. We solve the big problem by breaking it into smaller copies of the same problem, writing the step-by-step rule, and finding the pattern in the results. The same approach is used in computer programs that call themselves to solve smaller cases.

The skill of this chapter is to look at a pattern and decide what kind of sequence it is, then use the right tools. Here is a plan you can follow:

Step 1. Write out the first few terms. Do not try to guess from one or two. Writing four or five terms makes the pattern visible.

Step 2. Test the differences. Subtract each term from the next. If every difference is the same, you have an AP, and the common difference is d.

Step 3. Test the ratios. If the differences are not constant, divide each term by the previous one. If every ratio is the same, you have a GP with common ratio r.

Step 4. If neither is constant, look for another pattern such as squares (1, 4, 9, 16), triangular numbers (1, 3, 6, 10), or a recursive rule that uses two earlier terms like the Fibonacci sequence.

Step 5. Write the rule as an explicit formula, and check it on the terms you already know.

Step 6. Use the rule to answer the question, and check that the answer makes sense in the situation.

Example 1. A plant is 12 cm tall and grows 3 cm every week. Heights: 12, 15, 18, … The differences are constant (3), so it is an AP with a = 12 and d = 3. After 10 weeks the height is a₁₁ = 12 + 10 × 3 = 42 cm. (The starting height is the first term, so after 10 weeks we need the 11th term.)

Example 2. A town has a population of 8 000 that increases by 10% each year. The ratio is 1.1 each year, so the populations 8 000, 8 800, 9 680, … form a GP with a = 8 000 and r = 1.1. After 3 years the population is 8 000 × 1.1³ = 8 000 × 1.331 = 10 648.

Example 3. Which grows faster after many steps, an AP that starts at 100 and adds 10, or a GP that starts at 1 and doubles? The AP is ahead at first, with 100 at step 1 against 1. After 10 steps, the AP has 100 + 9 × 10 = 190 and the GP has 2⁹ = 512. After 20 steps the AP has 290 and the GP has 2¹⁹ = 524 288. The GP overtakes quickly and then leaves the AP far behind.

Computational thinking. Notice how this method follows the idea of an algorithm: a clear series of steps, each of which can be checked. A computer could carry out the plan for any sequence. When you describe a pattern in steps, test it on examples and refine it, you are thinking like a programmer and like a mathematician.