Problem Solving

Strong Induction

Students build a new step using several earlier blocks.

Strong Induction definition

Strong induction proves an indexed claim by allowing the inductive step to use every earlier case in the stated range.

In Spanish
inducción fuerte
Topic
Proof techniques

Strong Induction in a picture

Strong Induction diagramA strong induction step can use P(k − 1) and P(k) when it proves P(k + 1).Verify the required starting casesA recurrence may need two starting valuesAssume every case through kUse one or several earlier casesProve the next case k + 1Then induction covers the full range
A strong induction step can use P(k − 1) and P(k) when it proves P(k + 1).

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

What may the strong induction step assume?

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.