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.

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