Encyclopedia > Three forms of mathematical induction
Proofs that a subset of { 1, 2, 3, ... } is in fact the whole set { 1, 2, 3, ... } by mathematical induction usually have one of the following three forms.
The basis for induction is trivial; the substantial part of the proof goes from case n to case n + 1.
The case n = 1 is vacuously true; the step that goes from case n to case n + 1 is trivial if n > 1 and impossible if n = 1; the substantial part of the proof is the case n = 2, and the case n = 2 is relied on in the trivial induction step.
The induction step shows that if P(k) is true for all k < n then P(n) is true (proof by complete induction); no basis for induction is needed because the first, or basic, case is a vacuously true special case of what is proved in the induction step. This form works not only when the values of k and n are natural numbers, but also when they are transfinite ordinal numbers; see transfinite induction.
Mathematicalinduction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers, or otherwise is true of all members of an infinite sequence.
A somewhat more general form of argument used in mathematical logic and computer science shows that expressions that can be evaluated are equivalent; this is known as structural induction.
This form of mathematicalinduction is actually a special case of the previous form because if the statement that we intend to prove is P(n) then proving it with these two rules is equivalent with proving P(n + b) for all natural numbers n with the first two steps.
Feeds |
Contact