I know this question has been posted before, there is a solution in my text-book for this question and also this is posted on so many websites with full solution but I still don't understand. So can someone please help me?
BASIS STEP: We can form postage of 12, 13, 14, and 15 cents using three 4-cent stamps, two
4-cent stamps and one 5-cent stamp, one 4-cent stamp and two 5-cent stamps, and three 5-cent
stamps, respectively. This shows that P (12), P (13), P (14), and P (15) are true. This completes
the basis step.
INDUCTIVE STEP: The inductive hypothesis is the statement that P (j )is true for 12 ≤ j ≤ k,
where k is an integer with k ≥ 15. To complete the inductive step, we assume that we can form
postage of j cents, where 12 ≤ j ≤ k. We need to show that under the assumption that P (k + 1)
is true, we can also form postage of k + 1 cents. Using the inductive hypothesis, we can assume
that P (k − 3) is true because k − 3 ≥ 12, that is, we can form postage of k − 3 cents using
just 4-cent and 5-cent stamps. To form postage of k + 1 cents, we need only add another 4-cent
stamp to the stamps we used to form postage of k − 3 cents. That is, we have shown that if the
inductive hypothesis is true, then P (k + 1) is also true. This completes the inductive step.
I am stuck at this part:
how did they get k> 15 ?
and i don't get how did they get P(k-3)
like can someone please explain this to me?
Best Answer
Another proof, which looks more intuitive for me. Let's assume we have a set of stamps to form the $k$ total. Let's denote $n$ and $m$ a number of 4-cents and 5-cents stamps correspondingly. $$n \cdot 4 + m \cdot 5 = k$$ We need to prove that we can make changes in this set to form the next amount $k + 1$. There are two cases. If $n$ > 0, then we'll replace one 4-cents stamp by one 5-cents stamp and get the next amount: $$(n - 1) \cdot 4 + (m + 1) \cdot 5 = k + 1$$ If $n = 0$, then we'll replace three 5-cents stamps by four 4-cents stamps and again get the next amount: $$(m - 3)\cdot 5 + 4 \cdot 4 = k + 1$$ Of course, in the second case we have to have $m \ge3$, that's why we need $k \ge 15$.