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$
  • $\begingroup$ How it is true for 7? $\endgroup$ – Tacet Dec 5 '14 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 Dec 5 '14 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$ – Qiaochu Yuan Dec 5 '14 at 19:26
  • $\begingroup$ Because you are referring to element $k-2$, $k-2$ has to be satisfied. $\endgroup$ – Tacet Dec 5 '14 at 19:26
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$

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.