what is wrong in my proof using simple induction?

Question

I will prove $p(n):\ $Any $n$-cent postage where $n \ge 12$ can be made up using $3$-cents and $7$-cents stamps.

My proof:(simple induction)

Base case: as $12= 3+3+3+3$. So it can be made using $3$-cent.

Inductive case: I am assuming that $n$ postage can be made using $3$-cent and $7$-cent, so I will proof that $(n+1)$ can be made using $3$-cent and $7$-cent.

As $n$ postage can be made using $3$-cent and $7$-cent, we can construct $(n+7)$-postage. Then we can construct$((n+7)-3)$-postage, then $((n+7)-3)-3)=(n+1)$.

For instance, $20$-postage can be made using $(7+7+3+3)$, so $((20+1)=(20+7)-3)-3)$.

I know it is may be wrong. But I can not realize why?

Another question is, how many base case is needed for strong induction? I don't know. Please explain be done by anyone.

Answer 1

HINT:

• $A_{12}=\{3,3,3,3\}$
• $A_{13}=\{3,3,7\}$
• $A_{14}=\{7,7\}$
• $A_{n}=A_{n-3}\cup\{3\}$

Use the first three bullets for the base-case, and the last bullet for the inductive step.

---

Side note:

The problem in your answer is reflected in "I will prove that $n+1$...".

You need to prove it for $n+3$ (after showing it for $n$, $n+1$ and $n+2$).

Answer 2

The problem with your proof is you are removing 3 cent stamps. Your initial case only contains four lots of 3 cent stamps. So after your inductive step occurs two times you have no 3 cent stamps left and you can not continue indefinitely. More generally you can not guarantee that any arbitrary case $n$ will have a 3 cent stamp to remove.

A simpler approach would be to have 3 initial cases for 12,13 and 14 and have an inductive step of add a 3 cent stamp.

Edit: If you don't want to have three bases and do it the easy way you need to demonstrate that every $n$ case is one of two cases and have two different inductive steps:

• The $n$ case has (at least) two 3 cent stamps and you can then increase by one like you describe.

• The $n$ case has (at least) two 7 cent stamps and you can then increase by one by removing two 7 cent stamps and adding five 3 cent stamps.

To show that you always have one of these two cases is significantly harder.