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.

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