Show that the postage of six cents or more can be achieved by using only 2-cent and 7-cent stamps by using strong induction.

I know the important step to keep in mind is: Induction step: If $P(m), P(m+1), P(m+2) \ldots P(k)$ is true then $P(k+1)$ is true as well for some $k > m$.

Base Step:
$P(6)$ is true because $6= 2+2+2$
$P(7)$ is true because $7= 7$
$P(8)$ is true because $8= 2+2+2+2$
$P(9)$ is true because $9= 2+7$

Inductive Step:
Hypothesis: $P(k-3), P(k-2), P(k-1)$, and $P(k)$ is true. We can form a postage of $k+1$ using postage for 2 cents and 7 cents.

I am really unsure what is next. Am I even right with the above steps


Using the ideas mentioned in the previous answers, you can simplify your base step and your induction step as follows:

Base Step:

P(6) is true because 6=2+2+2

P(7) is true because 7=7

Inductive Step:

Let $k\ge7$, and assume that P(m) is true for all integers m with $6\le m\le k$.

Since $6\le k-1\le k$, we know that P(k-1) is true;

so $k-1=2a+7b$ for some integers $a,b\ge0$.

(Now finish the proof by using this equation to show that P(k+1) is true.)

  • $\begingroup$ I do not understand. What equation are you talking about? do you mean i do: k+1=2a+7b? How do I go to the next step? $\endgroup$ – Natasha Jul 7 '13 at 18:55
  • $\begingroup$ If you add 2 to both sides, you will get that $k+1=2(a+1)+7b$ where $a+1\ge0$ and $b\ge0$, which shows that P(k+1) is true. $\endgroup$ – user84413 Jul 7 '13 at 22:03
  • $\begingroup$ Thank you! That really helps! $\endgroup$ – Natasha Jul 7 '13 at 22:47
  • $\begingroup$ As you can see, Eric's answer gives the intuitive idea behind this proof. $\endgroup$ – user84413 Jul 7 '13 at 23:17

When I was first learning how to do inductive proofs, I often found myself getting lost in the formal rigor of the argument, and discovered that it was sometimes useful for me to step back and try to think about the process intuitively (intuitively for someone who did not yet find induction intuitive, that is...)

You're allowed to use the number 2, so if you have any number k, you can get to k+2, k+4, etc., which is to say every other number. If you also have k+1, you can use 2 to get k+3, k+5, etc. So if you've got any two consecutive numbers k and k+1, you can get any number k+2 or larger.

You saw that you can get 6 (out of three 2's), and you have 7 as well. So you can get any number bigger than 7 now, right? Either by adding 2's to 6 if the number is even, or 2's to 7 if the number is odd.

That is a (hopefully) intuitive approach to understand why the claim is true. You already have all of the mechanics written out for the formal inductive proof. Can you finish it from here?

  • $\begingroup$ I am unsure of the next step. I proved k+1 by using math. How do you wrap everything up? Thank you for explaining it....so now I understand it intuitively as well, which I do think is the point of the problem. $\endgroup$ – Natasha Jul 7 '13 at 16:14
  • $\begingroup$ @Natasha, user84413's answer below is an example of a formal writeup of this proof. Informally, you have already done it (you know that if you can write $k$ and $k+1$ then you can write any $j>k$, and you know that you can write 6 and 7). $\endgroup$ – Eric Kightley Jul 7 '13 at 16:52

Your problem seems to be that of your inductive step. With strong induction, your result is far stronger. You have that given $P(k), P(k+1)$, then $P(m)$ is true for all $m \ge k$.

Why? Well note that both $P(6)$ and $P(7)$ is true, because $6=2+2+2$ and $7=7$ (as you note). Now if we added another $2$-cent stamp, we can achieve $8$ and $9$. Then adding another, we can achieve $10$ and $11$, and so on.

  • $\begingroup$ I understand this, but I am unsure on the next step. I only know how to get thing started and to use math to prove k+1. What do I prove next? $\endgroup$ – Natasha Jul 7 '13 at 16:15

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.