linguistic:paraphrasing, structural:scholar_edition
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 P (m + 1) {\displaystyle P(m+1)} under the assumption that P (n) {\displaystyle P(n)} holds for all natural numbers n {\displaystyle n} less than m + 1 {\displaystyle m+1}; by contrast, the basic form only assumes P (m) {\displaystyle P(m)}. 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, P (0) {\displaystyle P(0)}, and it may even be necessary to prove extra-base cases such as P (1) {\displaystyle P(1)} before the general argument applies, as in the example below of the Fibonacci number F n {\displaystyle F_{n}}.

Although the form just described requires one to prove the base case, this is unnecessary if one can prove P (m) {\displaystyle P(m)} (assuming P (n) {\displaystyle P(n)} for all lower n {\displaystyle n}) for all m ≥ 0 {\displaystyle m\geq 0}. 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 m = 0 {\displaystyle m=0}, where P (0) {\displaystyle P(0)} is proved with no other P (n) {\displaystyle P(n)} assumed; this case may need to be handled separately, but sometimes the same argument applies for m = 0 {\displaystyle m=0} and m > 0 {\displaystyle m>0}, making the proof simpler and more elegant.In this method, however, it is vital to ensure that the proof of P (m) {\displaystyle P(m)} does not implicitly assume that m > 0 {\displaystyle m>0}, e.g. by saying "choose an arbitrary n < m {\displaystyle n<m} ", or by assuming that a set of m elements has an element.