##  [Strong Induction](/strong-induction-0) 

 Definition

A variant of induction where, to prove P(n+1), one assumes P(k) holds for all k ≤ n (the full set of smaller cases) rather than only assuming P(n); thus the inductive hypothesis is stronger and can use cumulative information from all previous instances.

 

 

 

 

 

 





## Principle

Principle

Cumulative hypothesis: the organizing idea is that allowing the full collection of earlier truths as hypotheses can enable proofs where a single-step implication is insufficient, often simplifying arguments that depend on several prior cases.

 

 

 

 

 





## Demonstration

Demonstration

Prove that every integer greater than 1 factors into primes: assume as induction hypothesis that every integer m with 2 ≤ m ≤ n factors into primes, then for n+1 either it is prime or it has a factorization into factors ≤ n, which by the hypothesis factor into primes; this uses all smaller instances.

 

 

 

 

## Misapplication

Misapplication

Invoking strong induction where ordinary induction suffices may obscure the minimal logical strength needed, or assuming strong induction grants non-well-founded reasoning beyond N; also misusing it without verifying the base range (e.g., starting too high).

 

 

 

 

 





## Consequence

Consequence

Provides a flexible proof tool that subsumes ordinary induction and supports proofs relying on several previous values, recurrence relations, and certain algorithmic correctness proofs; it clarifies dependence on earlier instances.

 

 

 

 

## Reversal

Reversal

The opposite is restricting to one-step induction only; some properties provable by strong induction may become awkward or require additional lemmas under ordinary induction, showing the difference in hypothesis strength.

 

 

 

 

 





## Boundary

Boundary

Applies on well-ordered successor domains like N; it is not automatically applicable to non-well-founded domains or to proofs that require transfinite induction without adapting the hypothesis to transfinite predecessors.

 

 

 

 

 





## Semantic Tension

Semantic Tension

Tension with economy of hypotheses: strong induction is logically equivalent to ordinary induction on N, but it feels stronger; the semantic tension lies between minimal assumptions and convenience of assuming the full prior corpus of truths.

 

 

 

 

 





## Synthesis

Synthesis

Strong induction is the induction form that permits assuming all smaller cases as hypotheses to prove the next case, streamlining proofs that need cumulative prior information while being, in N, equivalent in power to ordinary induction.