Home > Complete induction
Strong induction, also known as complete induction, is a variant on the principle of mathematical induction. The inductive hypothesis, instead of being simply -
is
- .
This is clearly a stronger hypothesis, hence the name strong induction. It is obvious that anything provable with regular induction is provable with strong induction.
On the other hand it requires only the introduction of a new proposition Q(n) which is the logical conjunction of the P(m) for 0 ≤ m ≤ n to write a strong induction argument as a conventional induction. This is sometimes done implicitly, as in minimal counterexample arguments by contradiction.
Mathematical logic Proofs
