Why is this Strong Inductions proof wrong?

Question

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.

Answer 1

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

Answer 2

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