I am so confused about this kind of question which is referring to amounts of money. I know we should use strong induction to prove if we meet some questions asking you which amounts of money can be formed using $n$ dollar bills and $k$ dollar bills?
For the example above, the question is asking you determine which amounts of postage can be formed using $4$-cent and $5$-cent stamps. Such that we know $4,5,8,9,10,12,13,14,15, \ldots$ can be formed using just $4$-cent and $5$-cent. Why for basis are we just using $12-15$ instead of using $4-9$?
Another example on the book(Discrete mathematics and its applications), determine which amounts of postage can be formed using just $4$-cent and $11$-cent stamps?
Same here, we know that $4, 8, 11, 12, 15, 16, 19, 20, 22, 23, 24, 26, 27, 28, \ldots$ can be formed using $4$-cent and $11$-cent stamps. Why do we want to prove $P(n)$ is true for all $n \geq 30$? I don't understand how to find the $j$ and $k$ (The Second Principle of Mathematical Induction: if (i) $P(a)$ is true for the starting point $a \in \mathbb{Z}^{+}$, and
(ii) (for any $k \in \mathbb{Z}^{+}$) if$ P(j)$ is true for any $j \in \mathbb{Z}^{+}$ such that $a \leq j \leq k$, then $P(k+1)$ is true, then $P(n)$ is true for all $n \in \mathbb{Z}^{+}, n \geq a$)?
Best Answer
This problem appears to be taken from Kenneth H. Rosen's text Discrete Mathematics and its Applications.
You have misstated the question in the example. What we need to prove is that every amount of postage of $12$ cents or more can be formed using just $4$-cent and $5$-cent stamps.
By showing that the four consecutive amounts $12$ cents, $13$ cents, $14$ cents, and $15$ cents can be formed using just $4$-cent and $5$-cent stamps, Rosen is providing a basis step for his strong induction argument that all amounts of $12$ cents or more can be formed using just $4$-cent and $5$-cent stamps. He wants to show that for $n \geq 16$ that since $n - 4 = 4j + 5k$ for some positive integers $j$ and $k$, then $n = 4(j + 1) + 5k$. Together with his demonstration that the amounts $12$ cents, $13$ cents, $14$ cents, and $15$ cents can be formed using only $4$-cent and $5$-cent stamps, this proves that all amounts of $12$ cents or more can be formed using just $4$-cent and $5$-cent stamps.
The reason Rosen starts at $12$ cents is that $12$ cents, $13$ cents, $14$ cents, and $15$ cents are the first four consecutive amounts that can be formed using only $4$-cent and $5$-cent stamps as it is not possible to form $11$ cents using only $4$-cent and $5$-cent stamps. Notice that the argument that if $n - 4 = 4j + 5k$ for some positive integers $j$ and $k$, then $n = 4(j + 1) + k$ cannot be applied when $n = 15$ since no such positive integers $j$ and $k$ exist for $n - 4 = 15 - 4 = 11$.
This is an example of the Frobenius coin problem. The English mathematician James Joseph Sylvester showed that the largest amount that cannot be formed using only $m$-cent and $n$-cent stamps with $\gcd(m, n) = 1$ is $mn - m - n$ cents. The number $mn - m - n$ is called the Frobenius number.
In our case, $m = 4$ and $n = 5$, so the largest amount that cannot be formed using only $4$-cent and $5$-cent stamps is $4 \cdot 5 - 4 - 5 = 11$ cents.
We want to prove $P(n)$ holds for $n \geq 30$ since it is not possible to form $4 \cdot 11 - 4 - 11 = 29$ cents using only $4$-cent and $11$-cent stamps.
Observe that \begin{align*} 30 & = 2 \cdot 4 + 2 \cdot 11\\ 31 & = (2 + 3) \cdot 4 + 1 \cdot 11\\ & = 5 \cdot 4 + 1 \cdot 11\\ 32 & = (5 + 3) \cdot 4 + 0 \cdot 11\\ & = 8 \cdot 4 + 0 \cdot 11\\ 33 & = (8 - 8) \cdot 4 + 3 \cdot 11\\ & = 0 \cdot 4 + 3 \cdot 11\\ \end{align*} Notice that in increasing from $n$ to $n + 1$, we either replace an $11$ by three $4$'s or we replace eight $4$'s with three $11$'s.
For $n \geq 30$, if