Find the flaw with the following \"proof\" that every postage of three cents or

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

Explanation / Answer

Solution:

The only flaw with this proof is that for j=5, the inductive step does not work as we can not form 5 cent postage from a combination of 3 cents & 4 cent postages.

For j>5 , the inductive steps work very well & holds true as:

3n that is multiple of 3 Example 3,6,9 etc.

3n+1 =>3(n-1)+4 with( n-1 )3 cent stamps & remaining 4 cent stamp. Example 4,7,9 etc.

3n+2 =>3(n-2)+4+4 with (n-2) 3 cent stamps & 2 4 cent stamps.(n>1)

Example:8, 11, etc.

But since the proof is not valid for n=1 for (3n+2) , the basis step as well as complete inductive analogy 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.