MISSION · Algebra
Recursive Sequences
Defining a sequence by how it moves rather than where it lands
LEVEL 1 · EXPLORE
Make the idea move
Change the controls and watch what happens. Follow your curiosity and see what you notice.
Loading the activity…
LEVEL 2 · LEARN
Unlock the explanation
Open the chapters in any order. Try the examples as you go.
The idea in one sentence
A recursive rule says how to get the next term from the previous one, so the sequence is described by its motion rather than by a formula for any term you like.
Two ways to say the same thing
Take \(3, 7, 11, 15, 19, \dots\)
The explicit formula gives any term straight from its position:
\[a_n = 4n - 1\]The recursive rule gives a starting point and a step:
\[a_1 = 3, \qquad a_n = a_{n-1} + 4\]Both describe the same sequence. The explicit one answers “what is the 500th term?” in one multiplication. The recursive one cannot, without computing all 499 before it.
So why ever use recursion? Because the step is often the thing you actually know.
The starting term is not optional
\(a_n = a_{n-1} + 4\) on its own describes infinitely many sequences — \(3, 7, 11, \dots\) and \(100, 104, 108, \dots\) and every other one with a gap of 4.
A recursive definition needs both parts: a base case and a rule. Leaving out the base case is the single most common error, and it makes the definition meaningless rather than merely incomplete.
For the same reason, Fibonacci needs two starting values, because its rule reaches back two places.
Fibonacci, and rules that reach further back
\[a_1 = 1, \quad a_2 = 1, \quad a_n = a_{n-1} + a_{n-2}\]giving \(1, 1, 2, 3, 5, 8, 13, 21, 34, \dots\)
There is no simple explicit formula here in the way there is for arithmetic and geometric sequences. One does exist — Binet’s formula, built out of \(\frac{1 + \sqrt 5}{2}\) — and it is startling that a rule about adding whole numbers should produce irrational ones in its closed form.
Fibonacci is the standard example of a sequence where the recursive definition is the natural one and the explicit formula is the afterthought. Ratios of consecutive terms approach the golden ratio \(\phi \approx 1.618\), which is why the numbers turn up in pinecones, sunflower heads and pineapple scales.
Converting between the forms
Going from recursive to explicit is straightforward when the rule is simple.
\(a_n = a_{n-1} + d\) is arithmetic, so \(a_n = a_1 + (n-1)d\). \(a_n = r \cdot a_{n-1}\) is geometric, so \(a_n = a_1 r^{n-1}\).
Anything more tangled generally has no elementary explicit form, and that is normal rather than a sign you have missed something.
Going the other way is always easy: subtract consecutive terms, or divide them, and the step falls out.
Where recursion is the honest description
- Compound interest. Next year’s balance is this year’s times 1.05. The explicit formula is a consequence, not the starting point.
- Population and drug dosing. Each period’s amount depends on the last one.
- Differential equations, which are the continuous version of exactly this idea: the rate of change depends on the current value.
- Programming. A function calling itself with a base case that stops it is the same structure, and forgetting the base case there causes the program to run forever.
- Mathematical induction, which proves things about recursive sequences by mirroring their shape: a base case and a step.
Common mix-ups
- Omitting the base case.
- Reading \(a_{n-1}\) as \(a_n - 1\). The first is the previous term; the second is this term minus one.
- Off-by-one on the index. Check whether the sequence starts at \(a_0\) or \(a_1\) before using any formula.
- Expecting an explicit formula to exist. Most recursive sequences have none in elementary terms.
- Using recursion for a far-off term by hand. That is what the explicit form is for.
Check yourself
With \(a_1 = 3\) and \(a_n = a_{n-1} + 4\), find \(a_4\). Say what the blank is in the Fibonacci rule, and which form gets you the 500th term fastest.
Stepping up: \(3, 7, 11, 15\), so \(a_4 = 15\). Fibonacci reaches back two, so the blank is \(a_{n-2}\). And the explicit formula gets term 500 in one step.
LEVEL 3 · REFLECT
Add this quest to your trail
When you feel ready, mark this idea as explored. You can always come back and try it again.
EXPLORER STRATEGIES