0

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.

Christian Blatter
  • 226,825
SKL
  • 9
  • 2
    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 04:44
  • 1
    Hint: Build 12, 13, and 14 by hand; only then you can automate. – vadim123 Sep 24 '16 at 04: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 04:54
  • 15=12+3, 16=13+3, 16=14+3, etc. – vadim123 Sep 24 '16 at 04:56
  • To dxiv: i know you are very tallent..please explain details and give me some example why i can to substract -3 ,if i don't use 3 to construct base case n. – SKL Sep 24 '16 at 05:36
  • 1
    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 07:06
  • "I will prove $p(n):\ $Any $n$-cent postage where $n \ge 12$ can be made up using $3$-cents and $7$-cents stamps." Actually you want to prove $p(n)$=[An $n$-cent postage can be made up using $3$-cents and $7$-cents stamps], for every $n \ge 12$. Can you see the difference? – Did Sep 24 '16 at 08:23
  • No.what is defference? – SKL Sep 24 '16 at 08:36
  • yahhh!!!!!!! i have understant the difference.. – SKL Sep 24 '16 at 09:10

2 Answers2

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

barak manos
  • 43,109
0

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.

Ian Miller
  • 11,844