Science Fair Project Encyclopedia
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
- P(n - 1),
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.
10-26-2009 08:16:03
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details