|
#REDIRECT[[mathematical induction]]
<!-- Please do not remove or change this AfD message until the issue is settled -->{{qif|test={{NAMESPACE}}|then=|else=}}
<div class="boilerplate metadata" id="afd" style="margin: 0 5%; padding: 0 7px 7px 7px; background: #EDF1F1; border: 1px solid #999999; text-align: left; font-size:95%;">
'''This article is being considered for deletion''' in accordance with Wikipedia's [[Wikipedia:Deletion policy|deletion policy]].<br />
Please share your thoughts on the matter at '''[[Wikipedia:Articles for deletion/{{{1|Three forms of mathematical induction}}}|this article's entry]]''' on the [[Wikipedia:Articles for deletion|Articles for deletion]] page.<br />
You are welcome to edit this article, but please do not blank this article or remove this notice while the discussion is in progress. For more information, particularly on merging or moving the article during the discussion, read the [[Wikipedia:Guide to deletion|Guide to deletion]].<br/>
<small>If you created the article, please don't take offense. Instead, please join the discussion and consider improving the article so that it meets the [[Wikipedia:Deletion policy|Wikipedia inclusion criteria]].</small><br/>
<div class="NavFrame" style="padding:0;border-style:none;"><div class="NavFrame" style="border-style:none;padding:0;"><div class="NavHead" style="background:#EDF1F1;text-align:left;"><span style="font-weight:normal;">[[Template:AfD in 3 steps|How to list a page for deletion]] ([{{fullurl:Wikipedia:Articles for deletion/Log/{{CURRENTYEAR}} {{CURRENTMONTHNAMEGEN}} {{CURRENTDAY}}|action=edit}} log])</span></div>
<div class="NavContent" style="display:none;background:#EDF1F1;">
{{AfD doc|{{{1|{{PAGENAME}}}}}}}
</div></div></div></div>
[[Category:Pages for deletion]]
<!-- End of AfD message, feel free to edit beyond this point -->
This article presumes familiarity with [[mathematical induction]]. This is not the appropriate place to learn what mathematical induction is or how to write proofs by mathematical induction. The article titled [[mathematical induction]], not this one, is the appropriate source of that kind of information.
==The three forms==
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. They are collected here in order to show the contrast between them, and its coexistence with the commonality between them.
===First form===
* The basis for induction is trivial;
* the substantial part of the proof goes from case ''n'' to case ''n'' + 1.
===Second form===
* The ''first'' case is [[vacuous truth|vacuously true]];
* the step that goes from the ''n''th case to the (''n'' + 1)th case is trivial if ''n'' ≥ 2 and impossible if ''n'' = 1;
* the substantial part of the proof is the ''second case'';
* the second case is relied on in the trivial induction step.
===Third form===
* 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 for ordinal numbers; see [[transfinite induction]].
==Examples==
This is not the appropriate place to go into details of proofs, but rather only broad outlines of proofs are shown. For examples of proofs by mathematical induction with full details, see [[mathematical induction]].
===First form===
Most proofs by mathematical induction that are adduced as examples when mathematical induction is first taught are of the first form.
===Second form===
====Product rule====
The usual [[product rule]] taught in [[calculus]] says
:<math>(fg)' = f'g + g'f.\,</math>
For a product of ''n'' functions, one has
:<math>(f_1 f_2 f_3 \cdots f_n)' \,</math>
::<math>= (f_1' f_2 f_3 \cdots f_n)
+ (f_1 f_2' f_3 \cdots f_n)
+ (f_1 f_2 f_3'\cdots f_n)+\cdots +(f_1 f_2 \cdots f_{n-1} f_n').\, </math>
In each of the ''n'' terms, just one of the factors is a derivative; the others are not.
Now observe four facts:
*If ''n'' = 1, then the proposition just says
::<math>f' = f'.\,</math>
:It can be said that just one factor is a derivative, and it is [[vacuous truth|vacuously true]] that the others are not, because there are no others!
*To go from case ''n'' to case ''n'' + 1 is trivial if ''n'' ≥ 2, but impossible if ''n'' = 1.
*To go from case ''n'' to case ''n'' + 1, one must ''use'' the case ''n'' = 2 (i.e. one must use the ordinary product rule taught in differential calculus).
*The substantial part of the proof is the case ''n'' = 2, and that is precisely the product rule that is taught differential calculus.
====Triangle inequality====
The usual [[triangle inequality]] in [[metric space]]s says
:<math>d(x_1,x_3) \le d(x_1,x_2) + d(x_2,x_3).\,</math>
For a sequence of ''n'' points, one has
:<math>d(x_1,x_n) \le d(x_1,x_2)+\cdots+d(x_{n-1},x_n).\,</math>
Now observe four facts
* The ''first'' case is
::<math>d(x_1,x_2) \le d(x_1,x_2),\,</math>
: and this is vacuously true, in that it does not rely on any information about what kind of function ''d'' is (i.e., that ''d'' is a metric).
* The ''n''th case is the case with ''n'' terms on the right side, and that is
::d(x_1,x_{n+1}) \le d(x_1,x_2) + \cdots + d(x_n, x_{n+1}).\,
: To go from there to the (''n'' + 1)th case is trivial if ''n'' ≥ 2, but impossible if ''n'' = 1.
* To go from case ''n'' to case ''n'' + 1, one must ''use'' the case ''n'' = 2 (i.e. one must use the ordinary triangle inequality).
* The substantial part of the proof is the ''second'' case. The second case is just the statement of the ordinary triangle inequality, and is different in different metric spaces. It is part of the proof that a particular function ''d'' is in fact a metric. In some cases is difficult or otherwise onerous. Usually the other aspects of proving that ''d'' is a metric are trivial (i.e. that ''d''(''x'', ''x'') = 0 for all ''x'', and that ''d'' is symmetric).
[More examples to be added.]
[[Category:Mathematical logic]][[Category:Proofs]]
| 