Sequences and Recurrence Relations
This topic covers sequences, which are ordered lists of numbers. ESAT questions will test your ability to generate terms from either an explicit formula for the nth term or from a recurrence relation, and 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.