# How to prove the inductive step in this Mathematical induction problem?

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

• P(3n) -> P(3(n+1)) – Peter Webb Feb 25 '15 at 7:43
• Check out this link which has an answer/proof for this exact question. Also, please typeset your questions correctly (I see you still refuse to learn how to correctly use $\LaTeX$ / MathJax). – Daniel W. Farlow Feb 25 '15 at 7:44
• what about 12, 15, 18, etc... – r0fg1 Feb 25 '15 at 7:47
• @crash Wait what? I typed out the question, did the thing for P(k), P(k+1). TB12 – committedandroider Feb 25 '15 at 7:48
• You can actually make a stronger hypothesis than that. Particularly, you can make a hypothesis about all postage amounts greater than 17. Hint: there are a few possibilities you missed in your pattern. – wgrenard Feb 25 '15 at 7:49

Starting with $0$ we can do all multiples of $3$, starting with $10$ we can do all numbers of the form $3k+1$ as well, and starting with $20$ we can do all numbers of the form $3k+2$ as well.