# 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$$.
Consider the case $$k=4$$! The only possibility in this case is one 4-cent stamp!