Three forms of mathematical induction: Difference between revisions

Revision as of 01:26, 14 April 2006

Latest revision as of 19:03, 29 April 2006

Line 1:

{{mergeto|Mathematical#REDIRECT[[mathematical induction}}]]

This article presumes that the reader knows what [[mathematical induction]] is and how to use it. The examples of proofs by mathematical induction given below are shown in broad outline, sometimes omitting detail, because the broad form is what is relevant in this article. For detailed examples, or for an introduction to this method of proof, see [[mathematical induction]].

==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 assumes the case ''n'' = ''k'' and deduces the case ''n'' = ''k'' + 1.

===Second form===

* The case ''n'' = 1 is [[vacuous truth|vacuously true]];

* the step that proves the case ''n'' = ''k'' + 1 is trivial, but relies on '''two''' previous cases: the case ''n'' = ''k'' and the case ''n'' = 2. This step cannot be used to prove the case ''n'' = 2 as to do so would be a [[circular argument]] (since the case ''n'' = 2 had not yet been proved).

* the substantial part of the proof is to give a (different) proof of the case ''n'' = 2.

===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 number]]s. 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 in secondary school 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>

: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''&nbsp;&ge;&nbsp;2, but impossible if ''n''&nbsp;=&nbsp;1.

*To go from case ''n'' to case ''n'' + 1, one must ''use'' the case ''n''&nbsp;=&nbsp;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 proof of 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

::<math>d(x_1,x_{n+1}) \le d(x_1,x_2) + \cdots + d(x_n, x_{n+1}).\,</math>

: To go from there to the (''n''&nbsp;+&nbsp;1)th case is trivial if ''n''&nbsp;&ge;&nbsp;2, but impossible if ''n''&nbsp;=&nbsp;1.

* To go from case ''n'' to case ''n'' + 1, one must ''use'' the case ''n''&nbsp;=&nbsp;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).

====Pólya's proof that there is no "horse of a different color"====

In the middle of the 20th century, a commonplace colloquial locution to express the idea that something is unexpectedly different from the usual was "''That's'' a horse of a different color!". [[George Pólya]] posed the following exercise: find the error in the following argument, which purports to prove by mathematical induction that all horses are of the same color:

:If there's only ''one'' horse, there's only one color.

:Suppose within any set of ''n'' horses, there is only one color. Now look at any set of ''n''&nbsp;+&nbsp;1 horses. Number them: 1, 2, 3, ..., ''n'', ''n''&nbsp;+&nbsp;1. Consider the sets {1, 2, 3, ..., ''n''} and {2, 3, 4, ..., ''n''&nbsp;+&nbsp;1}. Each is a set of only ''n'' horses, therefore with each there is only one color. But the two sets overlap, so there must be only one color among all ''n''&nbsp;+&nbsp;1 horses.

Now observe four facts

* The ''first'' case&mdash; with only one horse&mdash;is and this is vacuously true; there are no counterexamples&mdash;two horses of different colors&mdash;because there are no examples at all of two horses.

* To go from the case of ''n'' horses to the case of ''n''&nbsp;+&nbsp;1 horses is trivial if ''n''&nbsp;&ge;&nbsp;2 (it is done above), but impossible if ''n''&nbsp;=&nbsp;1.

:('''Spoiler:''' the impossibility when ''n'' = 1 is precisely the error that Polya challenged the student to find).

* To go from case ''n'' to case ''n'' + 1, one must ''use'' the fact that any ''two'' horses within either of the two sets of ''n'' are of the same color, i.e., one must use the case ''n''&nbsp;=&nbsp;2.

* The substantial part of the proof is the ''second'' case, i.e. the hard part is to prove that any '''two''' horses are of the same color. Once you've got that, it follows easily, by Polya's argument, that any set of ''more than two'' are of the same color.

[[Category:Mathematical logic]]

[[Category:Proofs]]