Note: This problem is from Discrete Mathematics and Its Applications [7th ed, prob 6, pg 342].

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

  • $\begingroup$ P(3n) -> P(3(n+1)) $\endgroup$ – Peter Webb Feb 25 '15 at 7:43
  • 1
    $\begingroup$ 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). $\endgroup$ – Daniel W. Farlow Feb 25 '15 at 7:44
  • $\begingroup$ what about 12, 15, 18, etc... $\endgroup$ – r0fg1 Feb 25 '15 at 7:47
  • $\begingroup$ @crash Wait what? I typed out the question, did the thing for P(k), P(k+1). TB12 $\endgroup$ – committedandroider Feb 25 '15 at 7:48
  • $\begingroup$ 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. $\endgroup$ – wgrenard Feb 25 '15 at 7:49

The following is obvious without a formal induction proof:

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.