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.