Course contentsShow
← Computer Science
Lesson 93 of 2,8722. Discrete Mathematics for CSFree lesson

Strong Induction

An enhanced form where the inductive hypothesis assumes truth for all values up to k, not just k.

Strong Induction

What You'll Learn

You'll learn a more powerful version of mathematical induction that lets you assume the truth of all earlier cases, not just the immediately preceding one.


The Core Idea

In regular induction (which you've learned), your inductive hypothesis assumes that a statement is true for some value k, then you prove it for k + 1. You're only looking one step back.

Strong induction gives you more to work with: you assume the statement is true for all values from the base case up through k, then prove it for k + 1. It's like having access to the entire history of true cases, not just the most recent one.

Structure of a Strong Induction Proof

  1. Base Case: Prove the statement for one or more initial values (just like before)
  2. Inductive Hypothesis: Assume the statement is true for all values from the base case up to some arbitrary k
  3. Inductive Step: Use any or all of those assumed cases to prove the statement for k + 1

When Is This Useful?

Strong induction shines when proving something for k + 1 requires looking back more than one step. For example:

  • Proving properties of the Fibonacci sequence (where F(n) = F(n-1) + F(n-2) depends on two previous terms)
  • Showing every integer ≥ 2 can be factored into primes
  • Analyzing algorithms with divide-and-conquer recurrences

Analogy

Regular induction is like climbing a ladder where each rung only depends on the one directly below it. Strong induction is like climbing where you can use any lower rung for support—much more flexible!


Key Takeaway: Strong induction assumes truth for all prior cases up to k, giving you a richer hypothesis to prove the next case—essential when problems naturally depend on multiple earlier values.