Question

Find the flaw with the following “proof” that every postage of three cents or more can be formed using just three-cent and four-cent stamps.

Basis Step: We can form postage of three cents with a single three-cent stamp and we can form postage of four cents using a single four-cent stamp.

Inductive Step: Assume that we can form postage ofj cents for all nonnegative integersj with$\mathit{j}\mathbf{\le }\mathit{k}$ using just three-cent and four-cent stamps. We can then form postage of$\mathit{k}\mathbf{+}\mathbf{1}$ cents by replacing one three-cent stamp with a four-cent stamp or by replacing two four-cent stamps by three three-cent stamps.

Short answer

The flaw with the proof is that each postages having$k+1$ number of cents can contain only two four cent or one three cent stamps.

Step-by-step solution

Significance of the induction

The induction is described as the process for proving a particular formula or theorem. Induction is also used for understanding the flaw inside a particular theorem.

Determination of the flaw

Here, from the basis and the inductive step, it can be identified that the four cents only consist of the stamp of four cent. No stamps of three cents are available in the four cent as the value ofk can only be 4 .

Thus, the flaw with the proof is that each postages having$k+1$ number of cents can contain only two four cent or one three cent stamps.