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 casen
did in fact use a 3-cent stamp. If it didn't, then you can't subtract that-3
. $\endgroup$ – dxiv Sep 24 '16 at 4:44why 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 give12=3+3+3+3
,13=7+3+3
,14=7+7
,15=7+7+7-3-3
. The latter is not a valid combination. $\endgroup$ – dxiv Sep 24 '16 at 7:06