# 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?

• $P(n+1)$ follows from $P(n-3)$, just add a $4$ cent stamp. – André Nicolas Feb 25 '15 at 5:32
• And that n-3 >= 21? – committedandroider Feb 25 '15 at 5:36
• And that $n-3\ge 18$. – André Nicolas Feb 25 '15 at 5:38
• $n+1$ starts at $22$. – André Nicolas Feb 25 '15 at 5:41
• So n >= 24, I thought the initial assumption was that n>=21? – committedandroider Feb 25 '15 at 5:44

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)$.

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.