Recurrences
Sequences defined step by step, and their shortcuts.
Pen and paper is fine · no calculator needed why?
Opens at level 42. You're level 1. You can read and practice here now.
the idea
A recurrence builds a sequence one term at a time from the terms before it. aₙ = 3aₙ₋₁ − 1 says: to get the next term, triple the last one and take away 1. Fibonacci adds the two terms before.
Stepping through works for a few terms, if you keep careful count of which term you are on. For terms far out, spot the pattern and use a closed form, a formula that gives the nth term directly. The Tower of Hanoi doubles its moves and adds one for each extra disk, which gives 2ⁿ − 1.
techniques
Step and label
- Write each term with its label: a₁, a₂, a₃, and so on.
- Apply the rule to the last term, or the last two for Fibonacci, to get the next.
- Stop at the label the question asks for.
worked example
a₁ = 3 and aₙ = 2aₙ₋₁ + 1. What is a₅?
- a₂ = 2 × 3 + 1 = 7.
- a₃ = 15, a₄ = 31, a₅ = 63.
Answer: 63
Double and add one
- To move n disks: move n − 1 aside, move the biggest, then move the n − 1 back on top.
- So each extra disk doubles the moves and adds one: 1, 3, 7, 15.
- That is one less than a power of 2: 2ⁿ − 1.
worked example
What is the minimum number of moves to solve the Tower of Hanoi with 8 disks?
- 2 to the power 8 is 256.
- 256 − 1 = 255.
Answer: 255
Spot the closed form
- Write the first four or five terms.
- Compare them with powers of 2, squares, or a start times powers of 3.
- Check it against the start and the rule: it must give the terms the rule gives. Then use it.
worked example
a₀ = 0 and aₙ = aₙ₋₁ + 2n − 1. What is a₁₂?
- Terms: 0, 1, 4, 9, 16, the squares.
- So aₙ = n², and a₁₂ = 12 × 12 = 144.
Answer: 144
watch out for
- Losing count of the terms. Starting from F₁, F₁₂ is the twelfth number you write.
- Going one step too far or stopping one short. Label every term as you write it.
- Forgetting the minus 1 in 2ⁿ − 1.
practice
Fibonacci
worked example
F₁ = F₂ = 1, and each term is the sum of the two before it. What is F₉?
Answer: 34
- Keep adding the last two terms: 1, 1, 2, 3, 5, 8, 13, 21, 34.
- So F₉ = 34.
Step through a rule
worked example
a₁ = 2 and aₙ = 3aₙ₋₁ − 1. What is a₅?
Answer: 122
- Apply the rule one step at a time: a₂ = 3 × 2 − 1 = 5.
- Then a₃ = 14, a₄ = 41, a₅ = 122.
Tower of Hanoi
worked example
What is the minimum number of moves to solve the Tower of Hanoi with 8 disks?
Answer: 255
- Moving n disks means moving n − 1 disks aside, the big one once, then the n − 1 back on top: the count doubles and adds one each time, giving 2ⁿ − 1.
- 2⁸ − 1 = 256 − 1 = 255.
Spot the formula
worked example
a₀ = 0 and aₙ = aₙ₋₁ + 2n − 1. What is a₂₄?
Answer: 576
- The terms go 0, 1, 4, 9, 16, …: adding the odd numbers 1, 3, 5, 7, … gives the squares, so aₙ = n².
- a₂₄ = 24² = 576.