Editing Mathematical induction (section)

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