# Error in induction proof

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.

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

## 1 Answer

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