Course contentsShow
← Mathematics
Lesson 2507 of 3,12150. Discrete Math — Logic and ProofFree lesson

Multiple Base Cases

Handling induction proofs that require verifying more than one initial case before the general step applies.

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:

  1. Identify how many previous cases your induction step relies on
  2. Verify all necessary base cases explicitly
  3. In the induction step, assume P(k), P(k-1), ..., P(k-m) all hold
  4. 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.