Note: This problem is from Discrete Mathematics and Its Applications [7th ed, prob 2, page 341].
Problem: Let $P(n)$ be the statement that a postage of n cents can be formed using just 4-cent stamps and 7-cent stamps. The parts of this exercise outline a strong induction proof that $P(n)$ is true for $n \geq 18$.
a) Show statements $P(18)$, $P(19)$, $P(20)$, $P(21)$ are true, completing the basis step of the proof
b) What is the inductive hypothesis of the proof?
c) What do you need to prove in the inductive step?
d) Complete the inductive step for $k \geq 21$.
I am currently working on 4d. I am trying to apply what I learned from
Brian M. Scott Strong Induction
My work(off Brian's Model):
$P(n)$ is the assertion that a postage of n cents can be formed using just 4-cent stamps and 7-cent stamps. I' am given $P(18), P(19), P(20)$, and $P(21)$ to get the induction started. Now I assume for some $n \geq 21$, $P(k)$ is true for each $k \leq n$. This is my induction hypothesis and my task in the induction step is to prove $P(n+1)$
So I have to prove $n + 1 = 7d + 4c$, with d and c being some natural number.
Where would I go from here? What Brian did in the last problem was use the relationship that a domino causes the domino three after it to fall to show that the n+1 domino has a domino three before it that is in the assumption.
How would you apply this idea here? There isn't really that sort of relationship here except except if you consider 18, 19, 20, and 21 are separated by one. Would you use that?
Let's take a look at the cases $n = 18, 19, 20, 21$.
\begin{align*} 18 & = 2 \cdot 7 + 4\\ 19 & = 7 + 3 \cdot 4\\ 20 & = 5 \cdot 4\\ 21 & = 3 \cdot 7 \end{align*} Note that as we increased from $18$ to $19$, we replaced one $7$ with two $4$'s. We did the same thing when we went from $19$ to $20$. When we went from $20$ to $21$, we replaced five $4$'s with three $7$'s.
Let $P(n)$ the statement that $n = 7k + 4l$ for some non-negative integers $k$ and $l$. Assume $P(m)$ holds for some $m \geq 21$. Then there exist non-negative integers $k$ and $l$ such that $m = 7k + 4l$. If $k > 0$, replace a $7$ by two $4$'s to obtain $m + 1 = 7(k - 1) + 4(l + 2)$. If $k = 0$, then $l \geq 5$ since $m \geq 21$. Thus, we can replace five $4$'s with three sevens to obtain $m + 1 = 3 \cdot 7 + 4(l - 5)$. Thus, $P(m) \Rightarrow P(m + 1)$.