Find the flaw with the following “proof” that every postage of three cents or mo

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
of j cents for all nonnegative integers j with j k using
just three-cent and four-cent stamps. We can then
form postage of k + 1 cents by replacing one three-cent
stamp with a four-cent stamp or by replacing two fourcent
stamps by three three-cent stamps.

Explanation / Answer

Basis step is correct.

Inductive step:

First mistake is to let je be all non negative integers <=k. But the hypothesis states 3 cents or more. So, j>=3

We are replacing:3 cent stamp with 4 cent stamp but there need not be a 3 cent stamp to replace with.

The alternate step to this is to replace two four cent stamps with three three-cent stamps. But there may not be two four-cent stamps. Eg. the 4 cents is formed by a single 4 cent stamp. So neither of the two cases work in this case. So the proof is incorrect.

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.