Induction / Recurrences
Least You Need to Know: Recurrences and Strong Induction
Recurrence claims often need **strong induction** because the next term depends on several earlier terms, not just one.
The least you need to know
- A recurrence defines later terms from earlier ones.
- If the step uses two previous values, you usually need two base cases.
- Strong induction lets you assume all earlier cases up to k.
- Check that the recurrence claim matches the domain of the sequence.
Key notation
a_n
the nth term of a sequence
a_n = a_{n-1}+a_{n-2}
a recurrence
P(1),…,P(k)
strong induction hypothesis
Tiny worked example
- Suppose `a_n = a_{n-1}+a_{n-2}` for `n≥3`.
- To prove a property of all terms, a strong induction step may use both `P(k)` and `P(k-1)`.
- That is why base cases for the first terms matter.
Common mistakes
- Students often try ordinary induction when the recurrence uses multiple earlier terms.
- Students often forget one needed base case.
- Students often use the recurrence before its starting index.
How to recognize this kind of problem
- Count how many earlier terms the recurrence references.
- Base cases should cover every term used before the induction starts.
- Strong induction is about having enough hypotheses available.
Next recommended lesson
Continue through this topic with Least You Need to Know: Strong Induction.
Least You Need to Know: Strong InductionRelated lessons
Keep going with nearby lessons in the same topic.