Chapter 2 · Sequences · Concept 5
2-26 Recurrence Relations and Induction
Three lessons gave you methods for rules of particular shapes. But aₙ₊₁ = (aₙ² − 1)/(n + 1) is none of those shapes, and no amount of rearranging will make it one. So you do what mathematicians actually do: work out a few terms, spot the pattern, and then prove you were right.
Guiding question
What do you do when no method fits the rule at all?
Learning outcome. Employ mathematical induction to prove and validate recurrence relations of sequences.
Guess, then prove
Step 1
Work out a₂, a₃, a₄ from the rule, and estimate the general term from what you see.
Step 2
Prove that estimate is correct, using mathematical induction.
The induction step looks slightly different here. In lesson 2-23 you built the k + 1 case out of the k case by adding a term. Here you build it using the recurrence relation — that is what tells you how to get from aₖ to aₖ₊₁.
So the step is: put your assumed aₖ into the rule, tidy, and check what comes out is the estimate with k + 1 in it.
These rules look forbidding. Their sequences do not — which is the whole reason the method works. Step through and watch the pattern appear.
Warm Up · a₁ = 3
For a₁ = 3 and aₙ₊₁ = (a2ₙ − 1)/(n + 1): find a₂, a₃, a₄, estimate the general term, and prove your estimate.
- 1
Walk the rule forward, putting n = 1.
a₂ = (32 − 1)/(1 + 1) = 8/2 = 4Square the term, take one away, divide by n + 1.
Work with a partner. One of you walks the terms out; the other writes the induction. Then check together that the step really used the recurrence, not just algebra.
Three numbers A, B, C in that order are in a geometric sequence with common ratio r. It is also true that A, 2B, C in that order are in an arithmetic sequence. Find the possible values of r.
How does mathematical induction let you confirm a formula you found by guessing from a recurrence — and why is the guessing not a weakness of the method?
Ask what the induction step actually uses.
Handing in the estimate on its own.
Part 1 is worth some marks; part 2 is worth the rest. "The pattern is obvious" proves nothing.
Not using the recurrence in the step.
Here the way from aₖ to aₖ₊₁ IS the rule. If your step never substitutes into it, it is not a proof about this sequence.
Comparing a₁ with your own working.
Part [1] compares the estimate at n = 1 with the first term the QUESTION gave. That is the only independent fact you have.
Expanding when you should factorise.
In the Warm Up, k² + 4k + 3 becomes (k+1)(k+3) and the (k+1) cancels. Leaving it expanded hides the answer.
Not tidying the step into the right shape.
Reaching k + 3 is not enough — write it as (k + 1) + 2 so it visibly matches the estimate at k + 1.
Sign In to Keep Going
You've reached the end of the free preview. Sign in — and upgrade to Plus or Pro — to keep going with Mathematics.
Full Access
Unlock all 105 lessons