Editing Mathematical induction (section)

=== Base case other than 0 or 1 ===
If one wishes to prove a statement, not for all natural numbers, but only for all numbers {{mvar|n}} greater than or equal to a certain number {{mvar|b}}, then the proof by induction consists of the following:
# Showing that the statement holds when {{math|1=''n'' = ''b''}}.
# Showing that if the statement holds for an arbitrary number {{math|''n'' ≥ ''b''}}, then the same statement also holds for {{math|''n'' +&thinsp;1}}.
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>

==== Example: forming dollar amounts by coins ====
Assume an infinite supply of 4- and 5-dollar coins. Induction can be used to prove that any whole amount of dollars greater than or equal to {{math|12}} can be formed by a combination of such coins. Let {{math|''S''(''k'')}} denote the statement "{{mvar|k}} dollars can be formed by a combination of 4- and 5-dollar coins". The proof that {{math|''S''(''k'')}} is true for all {{math|''k'' ≥ 12}} can then be achieved by induction on {{mvar|k}} as follows:

''Base case:'' Showing that {{math|''S''(''k'')}} holds for {{math|1=''k'' = 12}} is simple: take three 4-dollar coins.

''Induction step:'' Given that {{math|''S''(''k'')}} holds for some value of {{math|''k'' ≥ 12}} (''induction hypothesis''), prove that {{math|''S''(''k'' +&thinsp;1)}} holds, too. Assume {{math|''S''(''k'')}} is true for some arbitrary {{math|''k'' ≥ 12}}. If there is a solution for {{mvar|k}} dollars that includes at least one 4-dollar coin, replace it by a 5-dollar coin to make {{math|''k'' +&thinsp;1}} dollars. Otherwise, if only 5-dollar coins are used, {{mvar|k}} must be a multiple of 5 and so at least 15; but then we can replace three 5-dollar coins by four 4-dollar coins to make {{math|''k'' +&thinsp;1}} dollars. In each case, {{math|''S''(''k'' +&thinsp;1)}} is true.

Therefore, by the principle of induction, {{math|''S''(''k'')}} holds for all {{math|''k'' ≥ 12}}, and the proof is complete.

In this example, although {{math|''S''(''k'')}} also holds for <math display="inline">k \in \{ 4, 5, 8, 9, 10 \}</math>, the above proof cannot be modified to replace the minimum amount of {{math|12}} dollar to any lower value {{mvar|m}}. For {{math|1=''m'' = 11}}, the base case is actually false; for {{math|1=''m'' = 10}}, the second case in the induction step (replacing three 5- by four 4-dollar coins) will not work; let alone for even lower {{mvar|m}}.