1
$\begingroup$

What is wrong with the following proof?

Is it the fact that 5, 6 , 7 was never verified (base cases) because we never set a bound for k?

Claim: Any integral amount of postage greater than or equal to 5 cents can be made by using only 3-cent and 5-cent stamps.

Proof: Base case: 5 cents postage can be made using one 5 cent stamp. Inductive step: Assume that 5, 6, . . . , k cents postage can be made using only 3-cent and 5-cent stamps. To make k + 1 cents postage, note that k + 1 = (k − 2) + 3. Since k − 2 ≤ k, the hypothesis of the inductive step implies that k − 2 cents postage can be made using only 3-cent and 5-cent stamps. By adding one more 3-cent stamp, we have a total of k + 1 cents postage using only 3-cent and 5-cent stamps. Thus, by strong induction, any integral amount of postage greater than or equal to 5 cents can be made by using only 3-cent and 5-cent stamps.

$\endgroup$
4
  • $\begingroup$ How it is true for 7? $\endgroup$
    – Tacet
    Commented Dec 5, 2014 at 19:22
  • $\begingroup$ It is not, but the proof doesn't check. It only checks 5 and then proceeds with the induction. I'm a little confused, maybe the error is in the k-2..? $\endgroup$
    – Zee
    Commented Dec 5, 2014 at 19:23
  • 2
    $\begingroup$ If you want to use strong induction and you also want the ability to subtract $3$, then you need to check three base cases, namely $5, 6, 7$, and of course you can't check $7$ because it's not true. $\endgroup$ Commented Dec 5, 2014 at 19:26
  • $\begingroup$ Because you are referring to element $k-2$, $k-2$ has to be satisfied. $\endgroup$
    – Tacet
    Commented Dec 5, 2014 at 19:26

1 Answer 1

1
$\begingroup$

To rewrite your inductive hypothesis:

If $j\geq 5$ and $j \leq k$, then $j$ cents of postage can be made using only 3-cent and 5-cent stamps.

In the key step you attempt to use the inductive hypothesis for $k-2$. You check that $k-2 \leq k$, but to use the hypothesis you would also need to know $k-2 \geq 5$... which is false when $k=6$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .