Note: This problem is from Discrete Mathematics and Its Applications [7th ed, prob 6, pg 342].
Problem:
a) Determine which amounts of postage can be formed using just $3$-cent and $10$-cent stamps.
b)Prove your answer to $(a)$ using the principle of mathematical induction. Be sure to state explicitly your inductive hypothesis in the inductive step
My work:
For part a, I was able to do this by writing out a pattern of amounts that can be formed with just $3$ cent and $10$ cent stamps $-0, 3, 6, 9, 10, 13, 16, 19, 20, \cdots $
From this pattern I determined that amounts of postage with digits that end with $0$, $3$, $6$, or $9$ can be formed using just $3$-cent and $10$-cent stamps.
For part b, My basis case was 0 and I showed that $0$ can be formed with $0$ $3$ cent stamps and $0$ $10$ cent stamps.
My inductive hypothesis was that for some integer $k$, $k \geq 0, k$ can be formed with just 3 cent and 10 cent stamps.
What I am confused about is what to do for the inductive step. I know that the inductive step is to show $P(k) \Rightarrow P(k + 1)$ but for this problem, $k + 1$ isn't necessarily going to be able to be formed by just $3$ cent and $10$ cent stamps, say 4 for instance.
Is there another way I can represent $k + 1$? The way I have it set up is
$\quad k = 3 a + 10b$ where $a$ and $b$ are some integer $\geq 0$
$\quad k + 1 = 3a + 10b + 1$
but then $k + 1$ isn't necessarily a linear combination of $3$ and $10$.....