Sequences and Recurrence Relations
Sequences are ordered lists of numbers, and ESAT questions test your ability to generate terms from either an explicit formula for the nth term or a recurrence relation, then spot patterns to find a specific term or a sum.
Part of the ESAT Mathematics 2 syllabus — revision for the Engineering and Science Admissions Test (ESAT), the UAT-UK admissions test for Cambridge, Imperial, Oxford and UCL.
Key points
- A sequence can be defined by an explicit formula, which lets you calculate any term directly from its position 'n'.e.g., un = 3n - 1
- Alternatively, a sequence can be defined by a recurrence relation, which defines each term using the previous one(s) and requires a starting value.e.g., xn+1 = 2xn + 5
- For recurrence relations, you must generate terms one by one. Be prepared to calculate the first 5-10 terms to confidently identify a repeating pattern or cycle.
- The structure of the recurrence relation dictates how to spot a cycle. If a term depends only on the previous term, a cycle starts when a single value repeats. If it depends on two previous terms, a cycle starts when a pair of consecutive values repeats.
- Questions often ask for a term with a very large index (like the 200th term), which is a strong signal that you should look for a short, repeating cycle.
Formulae
un = f(n) This represents an explicit formula for the nth term. Use it to find a term directly without needing to calculate previous ones.
xn+1 = f(xn) This represents a simple recurrence relation. Use it to find the next term in a sequence when you know the current term.
Definitions
- Sequence
- An ordered list of numbers, called terms, that follow a specific rule.
- nth Term Formula
- An explicit rule, written in terms of 'n', that allows direct calculation of any term in a sequence given its position.
- Recurrence Relation
- An iterative rule that defines a term in a sequence based on the value of one or more preceding terms. It always requires one or more initial terms to be stated.
Worked example
A sequence is defined by x1 = 3 and the recurrence relation xn+1 = (xn)2 + 5. What is the units digit of the term x2024?
- 1
The term number (2024) is large, so we should look for a repeating pattern in the units digits.
- 2
Calculate the first few terms and track their units digits:
- 3 x1 = 3
Units digit is 3.
- 4 x2 = 32 + 5 = 9 + 5 = 14
Units digit is 4.
- 5 x3 = (unit digit 4)2 + 5 = 16 + 5 = 21
Units digit is 1.
- 6 x4 = (unit digit 1)2 + 5 = 1 + 5 = 6
Units digit is 6.
- 7 x5 = (unit digit 6)2 + 5 = 36 + 5 = 41
Units digit is 1.
- 8
The units digit of x3 was 1, and the units digit of x5 is also 1.
Since xn+1 only depends on xn, the pattern of units digits will now repeat.
- 9
The sequence of units digits is 3, 4, 1, 6, 1, 6, ⋯
The repeating cycle is (1, 6), which has a length of 2.
This cycle starts from the 3rd term.
- 10
We need the units digit of x2024.
The first two terms (3, 4) are not in the main cycle.
For n ≥ 3, the units digit is 1 if n is odd, and 6 if n is even - 11
Since 2024 is an even number and 2024 ≥ 3, the units digit of x2024 will be 6.
Answer: 6
Common mistakes
- ×A single arithmetic error when calculating the next term from a recurrence relation will corrupt all subsequent terms and prevent you from seeing the correct pattern.
- ×Mistaking the start of a cycle. Write out enough terms to be certain the pattern is established before making deductions about high-numbered terms.
- ×Concluding a sequence is constant or simple too early. Always calculate a few more terms than you think you need to confirm your hypothesis.
No-calculator tips
- ✓If only the units digit or remainder is required, perform all your iterative calculations using only the units digits or remainders. This avoids dealing with large, unwieldy numbers.
- ✓When faced with a complex recurrence relation, write each step down neatly. Trying to hold multiple intermediate values in your head is a common source of error under time pressure.