Question: Tom only have 2 type of coins: coins: 4 cents and 5 cents. Write a proof by induction that every amount n ≥ a can indeed be paid with Tom coins
1) Base Case: Tom can pay $12, $13, $14, $15, $16 and $17
2) Inductive steep: Let n>= 17 and suppose the Tom can pay every amount k with 12 <= k < n
3) Proof of claim: I am confused now...
edit: it's a normal induction, not strong induction
On
Normal induction includes strong induction.
But consider this:
Assume $k = 4a + 5b$.
Case 1: $a > 0$ then $k+1 = 4a + 5b+1 = 4a + 5b + 5 -4 = 4(a-1) + 5(b+1)$. Done.
Case 2: $a = 0$ but $k > 2$, then $k +1 =4a + 5b +1 = 4a + 5b + 16-15 = 4(a+4) + 5(b-3)$. Done.
Case 3: $a = 0$ and $k \le 2$ then $k\le 10$ and ... that's not a concern.
======
This is a good example of strong induction.
Suppose you know you can do it for ALL cases $12 \le n \le k$. And $k \ge 17$. Then you can do it for $k-4$. And if you can do it for $k -4$ you can do it for $k -4 +5 =k+1$ simply by doing what you did for $k-4$ and adding a $5$ cent coin.
Consider your next case where $n \ge 17.$ you can subtract $5$ and get $12$ (already done by earlier case.) If $n=18$ subtract $5,$ and so on up to $22.$ Keep going in such groups of six.