What's the flaw in the following “proof” by strong induction that every postage of 3 cents or more can be formed using only 3-cent and 4-cent stamps?

P(k): postage of k cents can be formed using only 3-cent and 4-cent stamps. Basis step: P(3): one 3-cent stamp. P(4): one 4-cent stamp.

Inductive step:

Assume P(j) is true for all positive integers 3 ≤ j ≤ k (Inductive Hypothesis).

To obtain postage for k + 1 cents we can consider the postage for k cents (by Inductive Hypothesis) and either replace one 3-cent stamp with a 4-cent stamp OR by replacing two 4-cent stamps with three 3-cent stamps.

Thus P(k+1) is true.

  • 1
    $\begingroup$ A good way to find a flaw in an induction proof is to look at the first case where it fails and then see where the induction step goes wrong in that case. $\endgroup$ – Eric Wofsey Nov 5 '19 at 3:56

You cannot do "replace one 3-cent stamp with a 4-cent stamp" when $k$ is $4$.

  • $\begingroup$ but if we have one 3 cent stamp then, this should do it for k = 4 right? $\endgroup$ – Xander Nov 5 '19 at 7:13
  • $\begingroup$ @Xander Yes, but actually no. The key is if we have one 3-cent stamp. But you cannot use one 3-cent stamp plus some 4-cent stamp to form 4-cent. The only way is to use one 4-cent stamp. $\endgroup$ – edm Nov 5 '19 at 7:18
  • $\begingroup$ but we can't use one 4 cent stamp? cuz if thats the case then, we cant get k = 3 either? cuz you cant have one 3 cent + 4 cent to get 3? $\endgroup$ – Xander Nov 6 '19 at 19:44
  • $\begingroup$ @Xander 3 cent is formed with exactly one 3-cent stamp and no 4-cent stamp, 4 cent is formed with exactly one 4-cent stamp and no 3-cent stamp. $\endgroup$ – edm Nov 7 '19 at 1:28
  • $\begingroup$ yeah so when k = 3, we one one 3 cent stamp, but when k = 4, you replace that one 3 cent stamp with one 4 cent stamp, so it should work ? $\endgroup$ – Xander Nov 8 '19 at 21:20

Consider the case $k=4$! The only possibility in this case is one 4-cent stamp!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.