The detective's method for sequences
Tonight's idea
Take a sequence and write the gaps between neighbours underneath it. These are the first differences. If they are all the same, the sequence is linear: the \(n\)th term is \(d \times n + c\), where \(d\) is the common difference and \(c\) is whatever makes the first term come out right.
If the first differences are not constant, take differences again. If the second differences are constant, the sequence is quadratic: its formula contains \(n^2\), and the number in front of \(n^2\) is half the second difference. Subtract that \(n^2\) part from the sequence and what is left is linear, which you already know how to handle.
Constant third differences mean a cube, and so on: the level at which the differences become constant tells you the degree.
Why does halving work? Look at the squares 1, 4, 9, 16, 25. First differences 3, 5, 7, 9. Second differences 2, 2, 2. So \(n^2\) on its own produces a second difference of 2; \(3n^2\) would produce 6; in general \(a n^2\) produces \(2a\). Divide by 2 to recover \(a\).
A warning. The differences only describe the terms you were shown. The next term can still be anything, because the sequence may not come from a polynomial at all. Question 5 is a famous trap.
Watch one: 2, 5, 10, 17, 26
| n | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| term | 2 | 5 | 10 | 17 | 26 |
| 1st diff | 3 | 5 | 7 | 9 | |
| 2nd diff | 2 | 2 | 2 |
Second differences are a constant 2, so the formula has \(\tfrac{2}{2} n^2 = n^2\) in it. Subtract \(n^2\) from each term: \(2 - 1 = 1\), \(5 - 4 = 1\), \(10 - 9 = 1\), \(17 - 16 = 1\), \(26 - 25 = 1\). What is left is the constant 1. So the \(n\)th term is \(n^2 + 1\). Check: \(n = 5\) gives \(26\).
Your turn
- 7, 11, 15, 19, 23. Take differences, state the kind of sequence, and write the \(n\)th term. Then find the 100th term.
- The triangular numbers 1, 3, 6, 10, 15 (see Gauss and the lazy sum). Show that the second differences are constant, find the \(n^2\) coefficient, subtract, and finish the formula. Does it agree with \(\tfrac{n(n+1)}{2}\)?
- 3, 8, 15, 24, 35. Find the \(n\)th term. Then factorise it. Compare each term with the square numbers 4, 9, 16, 25, 36. What do you notice?
- 1, 8, 27, 64, 125, 216. Keep taking differences until they are constant. How many levels did it take, and what does that tell you about the formula? (You may recognise the sequence anyway. The method should agree.)
- The trap. Put \(n\) dots on a circle and join every pair with a straight line, so that no three lines cross at a single point. Count the regions inside the circle. For \(n = 1, 2, 3, 4, 5\) you get 1, 2, 4, 8, 16. What would most people guess for \(n = 6\)? Draw it carefully with six dots and count.
Four dots, six chords, eight regions. Spread the dots unevenly so no three chords meet at one point.
Stretch: the real formula for the circle
The true sequence for the circle regions is 1, 2, 4, 8, 16, 31, 57, 99. Take differences all the way down and find at which level they become constant. What degree is the formula?
Write \(\binom{n}{k}\), said "\(n\) choose \(k\)", for the entry in row \(n\), position \(k\) of Pascal's triangle (positions counted from 0). The formula is \(\binom{n}{4} + \binom{n}{2} + 1\). Check it for \(n = 1\) to \(7\) by reading the entries off the triangle. Then explain the shape of the formula: each crossing point inside the circle comes from choosing 4 of the dots (why?), and each chord from choosing 2.
Answers
- Differences 4, 4, 4, 4: linear. \(4n + c\), and \(4 \times 1 + c = 7\) gives \(c = 3\). \(n\)th term \(4n + 3\). The 100th term is \(403\).
- First differences 2, 3, 4, 5; second differences 1, 1, 1. Coefficient \(\tfrac{1}{2}\). Subtracting \(\tfrac{1}{2}n^2\): \(1 - 0.5 = 0.5\), \(3 - 2 = 1\), \(6 - 4.5 = 1.5\), \(10 - 8 = 2\): that is \(\tfrac{1}{2}n\). Total \(\tfrac{1}{2}n^2 + \tfrac{1}{2}n = \tfrac{n(n+1)}{2}\). Yes.
- First differences 5, 7, 9, 11; second differences 2. Coefficient 1. Subtract \(n^2\): 2, 4, 6, 8, 10, which is \(2n\). \(n\)th term \(n^2 + 2n = n(n + 2)\). Each term is one less than a perfect square: \(3 = 4 - 1\), \(8 = 9 - 1\), \(15 = 16 - 1\). Indeed \(n(n+2) = (n+1)^2 - 1\).
- First differences 7, 19, 37, 61, 91; second 12, 18, 24, 30; third 6, 6, 6. Three levels, so the formula is cubic. It is \(n^3\).
- Most people guess 32. The true count for six dots is 31. The doubling pattern was an accident of the first five terms.
Stretch. First differences 1, 2, 4, 8, 15, 26, 42; second 1, 2, 4, 7, 11, 16; third 1, 2, 3, 4, 5; fourth 1, 1, 1, 1. Constant at the fourth level, so the formula is a quartic (has \(n^4\)). Checks: \(n = 4\): \(1 + 6 + 1 = 8\). \(n = 5\): \(5 + 10 + 1 = 16\). \(n = 6\): \(15 + 15 + 1 = 31\). \(n = 7\): \(35 + 21 + 1 = 57\). (For \(n = 1, 2, 3\) the \(\binom{n}{4}\) term is 0.) Every crossing inside the circle is where two chords meet, and two crossing chords have four distinct endpoints on the circle; conversely any 4 dots give exactly one crossing (join them as a quadrilateral and take the diagonals). So crossings are \(\binom{n}{4}\) and chords are \(\binom{n}{2}\). Starting from one region, each chord adds a region and each crossing adds one more. Hence the formula.