Editing Mathematical induction (section)

==== 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}}.