Editing Mathematical induction (section)

=== {{anchor|Complete 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 induction 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 induction step.

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; 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 {{mvar|m}} elements has an element.
====Equivalence with ordinary induction====
Complete induction is equivalent to ordinary mathematical induction as described above, in the sense that a proof by one method can be transformed into a proof by the other. Suppose there is a proof of <math>P(n)</math> by complete induction. Then, this proof can be transformed into an ordinary induction proof by assuming a stronger inductive hypothesis. Let <math>Q(n)</math> be the statement "<math>P(m)</math> holds for all <math>m</math> such that <math>0\leq m \leq n</math>"—this becomes the inductive hypothesis for ordinary induction. We can then show <math>Q(0)</math> and <math>Q(n + 1)</math> for <math>n \in \mathbb N</math> assuming only <math>Q(n)</math> and show that <math>Q(n)</math> implies <math>P(n)</math>.<ref>{{cite web |title=Proof:Strong induction is equivalent to weak induction |url=https://courses.cs.cornell.edu/cs2800/wiki/index.php/Proof:Strong_induction_is_equivalent_to_weak_induction |website=[[Cornell University]] |access-date=4 May 2023}}</ref>

If, on the other hand, <math>P(n)</math> had been proven by ordinary induction, the proof would already effectively be one by complete induction: <math>P(0)</math> is proved in the base case, using no assumptions, and <math>P(n+1)</math> is proved in the induction step, in which one may assume all earlier cases but need only use the case <math>P(n)</math>.

==== Example: Fibonacci numbers ====
Complete induction is most useful when several instances of the inductive hypothesis are required for each induction step. For example, complete induction can be used to show that
<math display="block"> F_n = \frac{\varphi^n - \psi^n}{\varphi - \psi}</math>
where <math>F_n</math> is the {{mvar|n}}-th [[Fibonacci number]], and <math display="inline">\varphi = \frac{1}{2}(1 + \sqrt 5)</math> (the [[golden ratio]]) and <math display="inline">\psi = \frac{1}{2} (1 - \sqrt 5)</math> are the [[root of a polynomial|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 \mathbb{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 ====
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 induction step, the induction hypothesis is that for a given <math>m>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 ====
We shall look to prove the same example as [[#Example: forming dollar amounts by coins|above]], this time with ''strong induction''. The statement remains the same:
<math display="block">S(n): \,\,n \geq 12 \implies \,\exists\, a,b\in\mathbb{N}. \,\, n = 4a+5b</math>

However, there will be slight differences in the structure and the assumptions of the proof, starting with the extended base case.

'''Proof.'''

''Base case:'' Show that <math>S(k)</math> holds for <math>k = 12,13,14,15</math>.
<math display="block">\begin{align}
4 \cdot 3+5 \cdot 0=12\\
4 \cdot 2+5 \cdot 1=13\\
4 \cdot 1+5 \cdot 2=14\\
4 \cdot 0+5 \cdot 3=15
\end{align}</math>

The base case holds.

''Induction step:'' Given some <math>j>15</math>, assume <math>S(m)</math> holds for all <math>m</math> with <math>12 \leq m< j</math>. Prove that <math>S(j)</math> holds.

Choosing <math>m=j-4</math>, and observing that <math>15 < j \implies 12 \leq j-4 < j</math> shows that <math>S(j-4)</math> holds, by the 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<ref name="yorku">.{{cite web |last1=Shafiei |first1=Niloufar |title=Strong Induction and Well-Ordering |url=https://www.eecs.yorku.ca/course_archive/2008-09/S/1019/Website_files/16-stong-induction-and-well-ordering.pdf |website=York University |access-date=28 May 2023}}</ref> Q.E.D.