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
Best Answer
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?