Question: "Find the flaw with the following "proof" that every postage of three pence or more can be formed using just three-pence and four-pence stamps.
Basis step: we can form postage of three pence with a single three-pence stamp and we can form postage of four pence using a single four-pence stamp.
Inductive step: assume we can form postage of $j$ pence for all integers $j$ where $3≤j≤k$ using just three-pence and four-pence stamps. We can then form postage of $k+ 1$ pence by replacing one three-pence stamp with a four-pence stamp or by replacing two four-pence stamps by three three-pence stamps."
I think the flaw is in the inductive step, as it doesn't show that postage of five pence can be formed. How could I explain this more formally?
Best Answer
The flaw is in the inductive step: nothing ensures that the set of stamps at step $k$ will contain a three-pence stamp or two four-pence stamps. The inductive step as it is written works only if one of these conditions is met.
[In fact, one can prove that it will be met for all $k$ except precisely $k=4$.]