Multiple Base Cases in Induction
What you'll learn: Sometimes an inductive proof requires you to verify more than one initial value before the induction step can safely proceed.
Why One Base Case Isn't Always Enough
In standard induction, you prove P(1) and then show P(k) → P(k+1). But some recursive relationships depend on multiple previous terms, not just the immediate predecessor. Think of the Fibonacci sequence: each term depends on the two terms before it. If you only verify F(1), you can't compute F(3) because you'd need F(2) as well.
When You Need Multiple Base Cases
You need multiple base cases when:
- Your induction step uses P(k-1), P(k-2), etc. (not just P(k))
- The problem naturally "skips" values (like proving something for all even numbers starting at n=2 and n=4)
- The recursive definition requires several starting values
The Method
Structure:
- Identify how many previous cases your induction step relies on
- Verify all necessary base cases explicitly
- In the induction step, assume P(k), P(k-1), ..., P(k-m) all hold
- Use those assumptions to prove P(k+1)
Example pattern: To prove F(n) = [(φⁿ - ψⁿ)/√5] for Fibonacci numbers:
- Base cases: Verify n=1 AND n=2
- Induction: Assume true for k-1 and k, then prove for k+1 using F(k+1) = F(k) + F(k-1)
Without both base cases, the induction step has no foundation—it's like trying to climb a ladder missing its bottom two rungs.
Key Takeaway: When your inductive step references multiple prior cases (like k and k-1), you must verify all those base cases before the induction "chain" can reliably extend forward.