Strong Induction definition
Strong induction proves an indexed claim by allowing the inductive step to use every earlier case in the stated range.
Strong Induction in a picture
How it works
Prove the starting cases needed by the argument. To prove the next case P(k + 1), assume P(n) for every n from the starting index through k. Use whichever earlier cases the proof requires. Strong and ordinary induction are equivalent proof principles over the natural numbers.
Worked examples
What earlier results may you use to prove P(10) if the claim starts at 1?
You may use any of P(1) through P(9).
Why does a prime factorization proof use strong induction?
A composite number splits into smaller factors. Both may be far below the preceding integer.
When a step uses the previous two cases, how many starting cases are often needed?
Two, so the first step has both required inputs.
Common mistake
Use only earlier cases in the hypothesis. Assuming the case you are proving would make the argument circular.
Quick check
Must the starting index be zero?
Show answer
No.
Is strong induction logically stronger over the natural numbers?
Show answer
No. It is an equivalent proof principle.
Sources
Flashcard
Strong Induction
Reveal the definition
Strong induction proves an indexed claim by allowing the inductive step to use every earlier case in the stated range.
Effortless Math. “Strong Induction.” Math Dictionary.
