How to come up with relation in induction hypothesis for strong induction 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?
 A: 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)$.
A: To prove a Strong Induction You need to prove the following:
For i ≤ k < j; Assuming P(k) holds, prove P(j) holds. For any i,j,k element of Natural Numbers.
For this question, we need to show that 21 ≤ k < j; P(j) holds assuming P(k) holds.
Basis: P(21), P(22), P(23), P(24)      (You have shown these, similar to part a)
Inductive Step:
To come up with your own inductive step is usually the hard part. Since I have done a lot of induction problems in University, I have developed a sense of what I need here.
Basically 21 ≤ k, we've already proved 21,22,23,24 holds by basis
We need to show P(25) holds. P(25) is simply P(21 + 4), P(21) holds by basis and 4 holds trivially because it is a 4 cent stamp.
   Likewise, this shows P(26)...P(28) holds, but wait! P(29) doest it hold...? YES!
P(29) = P(22) + 7 and 7 holds trivially again, due to 7 cent stamp.
However... eveything above was just the thinking process, we need now show P(j) holds.
P(j) can be recursively defined as P(k+ 4n) or P(k+7n) where n is recursive depth, and because P(k) holds and k < j; we have shown P(j) holds for all natural number j. 
