Lab: Strong Mathematical Induction

Consider the following classic numeric problem regarding making change:

Suppose that you live in a country where currency only comes in 3¢ and 10¢ denominations. Show that you can form any amount of money $n$ from 3¢ and 10¢ pieces as long as $n\ge 18$.

Let us attempt to prove this claim by induction. Really, the claims says that we can choose $x$ and $y$, such that $3x+10y=n$ as long as $n\ge 18$. $x$ and $y$ here are the number of 3¢ and 10¢ pieces, respectively.

1. Attempt to prove this claim by mathematical induction. Push the proof through as much as possible until you get stuck. Identify you get stuck and why you cannot make any more progress.

2. Since the proof did not work out, you might be tempted to believe that the claim is actually false; not an unreasonable conclusion. However, it turns out this claim is actually true. Develop a series of examples for $n=18$ through $n=26$ (9 examples in all) to convince yourself that this is the case.

3. Sometimes, a particular proof technique is not strong enough to prove a proposition. In these situations, we must resort to a different proof technique better suited for the situation at hand.

   Rather than using regular mathematical induction, we'll invoke a variant of mathematical induction, strong induction, to prove this claim.

   Definition (Strong Induction): strong induction is a proof principle that is like mathematical induction, i.e., induction over a natural number $n$, except that we assume that our induction hypothesis holds for any natural number $k<n$.

   Regular mathematical induction allows us to handle situations where our recursive definitions decrease by one on each step. Strong induction allows us to handle situations where our recursive definitions steps by more than just one and more generally, in irregular patterns.

   Practically speaking, to use the strong induction principle:

   • We state that we are using strong induction instead of regular induction.
   • We change our induction hypothesis to reflect the fact that the hypothesis holds for any natural number $k<n$ rather than just $n-1$.
   • Finally, we also may need to include additional base cases to account for the potentially irregular pattern that our inductive object decreases by.

   Change your original, incomplete inductive proof to a strong induction proof and complete it.

   (Hint 1: now your induction hypothesis holds for any number less than $n$. Don't overthink this part! Choose a convenient target value that is less than $n$ that you can apply your induction hypothesis to.)

   (Hint 2: now think about how much you decrease $n$ by in each inductive step. A single base case of $n=18$ is no longer sufficient because you are no longer decreasing by one. What additional base cases do you need?)

4. Once you are done, you might think this proof feels "too simple!" In some sense it is because the corresponding algorithm for making change implied by this proof is also straightforward! In a sentence or two, describe the algorithm for making change that is suggested by your reasoning. This final bit highlights the connection between proving and algorithmic design. We can design an algorithm with correctness in mind; dually, we often can derive an algorithm from our reasoning!