# what is wrong in my proof using simple induction?

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.

• As n postage can be made using 3-cent and 7-cent,we can construct (n+7)pastage.then we can construct((n+7)-3)prostage You don't know that the base case n did in fact use a 3-cent stamp. If it didn't, then you can't subtract that -3. – dxiv Sep 24 '16 at 4:44
• Hint: Build 12, 13, and 14 by hand; only then you can automate. – vadim123 Sep 24 '16 at 4:48
• Hi guys,thank you.But can you explain me.why it is this 3 case is needed by hand?why not 4,5,6........?I know it is the base case of strong induction.But i can not realize clear concept of this induction. – SKL Sep 24 '16 at 4:54
• 15=12+3, 16=13+3, 16=14+3, etc. – vadim123 Sep 24 '16 at 4:56
• why i can to substract -3 ,if i don't use 3 to construct base case n There are already a couple of answers posted which answer this, and I can't do better than them in a short comment. Basically, your proof doesn't cover the possibility that later on you would have a sum made up only of $7$-cent stamps, and in that case your induction step fails. Just walk what you posted step by step. It would give 12=3+3+3+3, 13=7+3+3, 14=7+7, 15=7+7+7-3-3. The latter is not a valid combination. – dxiv Sep 24 '16 at 7:06

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$).

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.