Proofs:Induction - Revision history

Khanh: /* Complete (strong) induction */

2021-11-06T21:58:02Z

Complete (strong) induction

Khanh at 21:56, 6 November 2021

2021-11-06T21:56:15Z

Lila at 19:43, 12 October 2021

2021-10-12T19:43:34Z

Lila at 19:42, 12 October 2021

2021-10-12T19:42:23Z

Lila: /* Example: prime factorization */

2021-10-12T19:41:46Z

Example: prime factorization

Lila: /* Example: Fibonacci numbers */

2021-10-12T19:40:55Z

Example: Fibonacci numbers

Lila: /* Example: Fibonacci numbers */

2021-10-12T19:40:24Z

Example: Fibonacci numbers

Lila: /* {{anchor|Complete induction}} Complete (strong) induction */

2021-10-12T19:39:50Z

{{anchor|Complete induction}} Complete (strong) induction

Lila: /* Prefix induction */

2021-10-12T19:39:20Z

Prefix induction

Lila: /* Infinite descent */

2021-10-12T19:38:19Z

Infinite descent

@@ Line 158: / Line 158: @@
 In fact, it can be shown that the two methods are actually equivalent, as explained below. In this form of complete induction, one still has to prove the base case, <math>P(0)</math>, and it may even be necessary to prove extra-base cases such as <math>P(1)</math> before the general argument applies, as in the example below of the Fibonacci number <math>F_{n}</math>.
-Although the form just described requires one to prove the base case, this is unnecessary if one can prove <math>P(m)</math> (assuming <math>P(n)</math> for all lower <math>n</math>) for all <math>m\geq 0</math>. This is a special case of [[#Transfinite induction|transfinite induction]] as described below, although it is no longer equivalent to ordinary induction. In this form the base case is subsumed by the case <math>m=0</math>, where <math>P(0)</math> is proved with no other <math>P(n)</math> assumed;
+Although the form just described requires one to prove the base case, this is unnecessary if one can prove <math>P(m)</math> (assuming <math>P(n)</math> for all lower <math>n</math>) for all <math>m\geq 0</math>. This is a special case of transfinite induction as described below, although it is no longer equivalent to ordinary induction. In this form the base case is subsumed by the case <math>m=0</math>, where <math>P(0)</math> is proved with no other <math>P(n)</math> assumed;
 this case may need to be handled separately, but sometimes the same argument applies for <math>m=0</math> and <math>m>0</math>, making the proof simpler and more elegant.
 In this method, however, it is vital to ensure that the proof of <math>P(m)</math> does not implicitly assume that <math>m>0</math>, e.g. by saying "choose an arbitrary <math>n<m</math>", or by assuming that a set of ''m'' elements has an element.

@@ Line 197: / Line 197: @@
 Choosing <math>m=j-4</math>, and observing that <math>15< j \to 12\leq j-4<j</math> shows that <math>S(j-4)</math> holds, by inductive hypothesis. That is, the sum <math>j-4</math> can be formed by some combination of <math>4</math> and <math>5</math> dollar coins. Then, simply adding a <math>4</math> dollar coin to that combination yields the sum <math>j</math>. That is, <math>S(j)</math> holds. Q.E.D.
-==Resources==
+== Licensing ==
-* [https://en.wikipedia.org/wiki/Mathematical_induction Mathematical induction], Wikipedia
+Content obtained and/or adapted from:

← Older revision		Revision as of 19:43, 12 October 2021
Line 196:		Line 196:

	Choosing <math>m=j-4</math>, and observing that <math>15< j \to 12\leq j-4<j</math> shows that <math>S(j-4)</math> holds, by inductive hypothesis. That is, the sum <math>j-4</math> can be formed by some combination of <math>4</math> and <math>5</math> dollar coins. Then, simply adding a <math>4</math> dollar coin to that combination yields the sum <math>j</math>. That is, <math>S(j)</math> holds. Q.E.D.		Choosing <math>m=j-4</math>, and observing that <math>15< j \to 12\leq j-4<j</math> shows that <math>S(j-4)</math> holds, by inductive hypothesis. That is, the sum <math>j-4</math> can be formed by some combination of <math>4</math> and <math>5</math> dollar coins. Then, simply adding a <math>4</math> dollar coin to that combination yields the sum <math>j</math>. That is, <math>S(j)</math> holds. Q.E.D.
		+
		+	==Resources==
		+	* [https://en.wikipedia.org/wiki/Mathematical_induction Mathematical induction], Wikipedia

@@ Line 99: / Line 99: @@
 This can be used, for example, to show that {{math|2<sup>''n''</sup> ≥ ''n'' + 5}} for {{math|''n'' ≥ 3}}.
-In this way, one can prove that some statement {{math|''P''(''n'')}} holds for all {{math|''n'' ≥ 1}}, or even for all {{math|''n'' ≥ −5}}. This form of mathematical induction is actually a special case of the previous form, because if the statement to be proved is {{math|''P''(''n'')}} then proving it with these two rules is equivalent with proving {{math|''P''(''n'' + ''b'')}} for all natural numbers {{mvar|n}} with an induction base case {{math|0}}.<ref>Ted Sundstrom, ''Mathematical Reasoning'', p. 190, Pearson, 2006, {{isbn|978-0131877184}}</ref>
+In this way, one can prove that some statement {{math|''P''(''n'')}} holds for all {{math|''n'' ≥ 1}}, or even for all {{math|''n'' ≥ −5}}. This form of mathematical induction is actually a special case of the previous form, because if the statement to be proved is {{math|''P''(''n'')}} then proving it with these two rules is equivalent with proving {{math|''P''(''n'' + ''b'')}} for all natural numbers {{mvar|n}} with an induction base case {{math|0}}.
 ==== Example: forming dollar amounts by coins ====

@@ Line 171: / Line 171: @@
 ====Example: prime factorization====
-Another proof by complete induction uses the hypothesis that the statement holds for ''all'' smaller <math>n</math> more thoroughly. Consider the statement that "every [[natural number]] greater than 1 is a product of (one or more) [[prime number]]s", which is the "[[Fundamental theorem of arithmetic#Existence|existence]]" part of the [[fundamental theorem of arithmetic]]. For proving the inductive step, the induction hypothesis is that for a given <math>n>1</math> the statement holds for all smaller <math>n>1</math>.  If <math>m</math> is prime then it is certainly a product of primes, and if not, then by definition it is a product: <math>m=n_1 n_2</math>, where neither of the factors is equal to 1; hence neither is equal to <math>m</math>, and so both are greater than 1 and smaller than <math>m</math>.  The induction hypothesis now applies to <math>n_1</math> and <math>n_2</math>, so each one is a product of primes. Thus <math>m</math> is a product of products of primes, and hence by extension a product of primes itself.
+Another proof by complete induction uses the hypothesis that the statement holds for ''all'' smaller <math>n</math> more thoroughly. Consider the statement that "every natural number greater than 1 is a product of (one or more) prime numbers", which is the "existence" part of the fundamental theorem of arithmetic. For proving the inductive step, the induction hypothesis is that for a given <math>n>1</math> the statement holds for all smaller <math>n>1</math>.  If <math>m</math> is prime then it is certainly a product of primes, and if not, then by definition it is a product: <math>m=n_1 n_2</math>, where neither of the factors is equal to 1; hence neither is equal to <math>m</math>, and so both are greater than 1 and smaller than <math>m</math>.  The induction hypothesis now applies to <math>n_1</math> and <math>n_2</math>, so each one is a product of primes. Thus <math>m</math> is a product of products of primes, and hence by extension a product of primes itself.
 ==== Example: dollar amounts revisited ====

@@ Line 168: / Line 168: @@
 :<math> F_n = \frac{\varphi^n - \psi^n}{\varphi - \psi}</math>
-where <math>F_n</math> is the ''n''th Fibonacci number, <math display="inline">\varphi = {{1 + \sqrt 5} \over 2}</math> (the [[golden ratio]]) and <math display="inline">\psi = {{1 - \sqrt 5} \over 2}</math> are the roots of the polynomial <math>x^2-x-1</math>. By using the fact that <math>F_{n+2} = F_{n+1} + F_{n}</math> for each <math>n \in \Bbb{N}</math>, the identity above can be verified by direct calculation for <math display="inline">F_{n+2}</math> if one assumes that it already holds for both <math display="inline">F_{n+1}</math> and <math display="inline">F_n</math>. To complete the proof, the identity must be verified in the two base cases: <math>n=0</math> and <math display="inline">n=1</math>.
+where <math>F_n</math> is the ''n''th Fibonacci number, <math display="inline">\varphi = {{1 + \sqrt 5} \over 2}</math> (the golden ratio) and <math display="inline">\psi = {{1 - \sqrt 5} \over 2}</math> are the roots of the polynomial <math>x^2-x-1</math>. By using the fact that <math>F_{n+2} = F_{n+1} + F_{n}</math> for each <math>n \in \Bbb{N}</math>, the identity above can be verified by direct calculation for <math display="inline">F_{n+2}</math> if one assumes that it already holds for both <math display="inline">F_{n+1}</math> and <math display="inline">F_n</math>. To complete the proof, the identity must be verified in the two base cases: <math>n=0</math> and <math display="inline">n=1</math>.
 ====Example: prime factorization====

@@ Line 153: / Line 153: @@
 whereupon the induction principle "automates" log log ''n'' applications of this inference in getting from ''P''(0) to ''P''(''n''). This form of induction has been used, analogously, to study log-time parallel computation.
-=== {{anchor|Complete induction}} Complete (strong) induction===
+===Complete (strong) induction===
 Another variant, called '''complete induction''', '''course of values induction''' or '''strong induction''' (in contrast to which the basic form of induction is sometimes known as '''weak induction'''), makes the inductive step easier to prove by using a stronger hypothesis: one proves the statement <math>P(m+1)</math> under the assumption that <math>P(n)</math> holds for ''all'' natural numbers <math>n</math> less than <math>m+1</math>; by contrast, the basic form only assumes <math>P(m)</math>. The name "strong induction" does not mean that this method can prove more than "weak induction", but merely refers to the stronger hypothesis used in the inductive step.

@@ Line 145: / Line 145: @@
 If traditional predecessor induction is interpreted computationally as an ''n''-step loop, then prefix induction would correspond to a log-''n''-step loop. Because of that, proofs using prefix induction are "more feasibly constructive" than proofs using predecessor induction.
-Predecessor induction can trivially simulate prefix induction on the same statement. Prefix induction can simulate predecessor induction, but only at the cost of making the statement more syntactically complex (adding a bounded [[universal quantifier]]), so the interesting results relating prefix induction to polynomial-time computation depend on excluding unbounded quantifiers entirely, and limiting the alternation of bounded universal and [[existential quantifier]]s allowed in the statement.<ref name=Buss:BA>{{cite book|last=Buss|first=Samuel|title=Bounded Arithmetic|date=1986|publisher=Bibliopolis|location=Naples}}</ref>
+Predecessor induction can trivially simulate prefix induction on the same statement. Prefix induction can simulate predecessor induction, but only at the cost of making the statement more syntactically complex (adding a bounded universal quantifier), so the interesting results relating prefix induction to polynomial-time computation depend on excluding unbounded quantifiers entirely, and limiting the alternation of bounded universal and existential quantifiers allowed in the statement.
 One can take the idea a step further: one must prove
@@ Line 151: / Line 151: @@
 :<math>\forall k \left( P \left( \left\lfloor \sqrt{k} \right\rfloor \right) \to P(k) \right)</math>
-whereupon the induction principle "automates" log log ''n'' applications of this inference in getting from ''P''(0) to ''P''(''n''). This form of induction has been used, analogously, to study log-time parallel computation.{{citation needed|date=January 2018}}
+whereupon the induction principle "automates" log log ''n'' applications of this inference in getting from ''P''(0) to ''P''(''n''). This form of induction has been used, analogously, to study log-time parallel computation.
 === {{anchor|Complete induction}} Complete (strong) induction===

@@ Line 121: / Line 121: @@
 ===Infinite descent===
-The method of infinite descent is a variation of mathematical induction which was used by [[Pierre de Fermat]]. It is used to show that some statement ''Q''(''n'') is false for all natural numbers ''n''. Its traditional form consists of showing that if ''Q''(''n'') is true for some natural number ''n'', it also holds for some strictly smaller natural number ''m''. Because there are no infinite decreasing sequences of natural numbers, this situation would be impossible, thereby showing (by contradiction) that ''Q''(''n'') cannot be true for any ''n''.
+The method of infinite descent is a variation of mathematical induction which was used by Pierre de Fermat. It is used to show that some statement ''Q''(''n'') is false for all natural numbers ''n''. Its traditional form consists of showing that if ''Q''(''n'') is true for some natural number ''n'', it also holds for some strictly smaller natural number ''m''. Because there are no infinite decreasing sequences of natural numbers, this situation would be impossible, thereby showing (by contradiction) that ''Q''(''n'') cannot be true for any ''n''.
 The validity of this method can be verified from the usual principle of mathematical induction.  Using mathematical induction on the statement ''P''(''n'') defined as "''Q''(''m'') is false for all natural numbers ''m'' less than or equal to ''n''", it follows that ''P''(''n'') holds for all ''n'', which means that ''Q''(''n'') is false for every natural number ''n''.