Content deleted Content added
m cats |
Hashproduct (talk | contribs) Added an example for the first kind of induction, as requested |
||
Line 2:
# The basis for induction is trivial; the substantial part of the proof goes from case ''n'' to case ''n'' + 1.
Theorem: For all nonnegative integers ''n'',
#The case ''n'' = 1 is [[vacuous truth|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.▼
1 + 2 + ... + ''n'' = ''n''(''n'' + 1)/2.
Proof: For ''n'' = 0, the statement is trivial: the sum has no terms and is 0, and the quantity on the right is also 0. Suppose the statement is true for ''n''. Add ''n'' + 1 to both sides and you get:
1 + 2 + ... + ''n'' + (''n'' + 1) = (''n'')(''n'' + 1)/2 + (2)(''n'' + 1)/2 = (''n'' + 1)(''n'' + 2)/2.
This is just the ''n'' + 1 version of the statement, and induction finishes the proof.
▲# The case ''n'' = 1 is [[vacuous truth|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 <i>P</i>(<i>k</i>) is true for all <i>k</i> < <i>n</i> then <i>P</i>(<i>n</i>) 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 <i>k</i> and <i>n</i> are natural numbers, but also when they are transfinite ordinal numbers; see [[transfinite induction]].
| |||