# Why is this Strong Inductions proof wrong?

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.

• 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. – 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$$.

• but if we have one 3 cent stamp then, this should do it for k = 4 right? – Xander Nov 5 '19 at 7:13
• @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. – edm Nov 5 '19 at 7:18
• 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? – Xander Nov 6 '19 at 19:44
• @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. – edm Nov 7 '19 at 1:28
• 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 ? – Xander Nov 8 '19 at 21:20

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