0
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – dxiv Sep 24 '16 at 4:44
  • 1
    $\begingroup$ Hint: Build 12, 13, and 14 by hand; only then you can automate. $\endgroup$ – vadim123 Sep 24 '16 at 4:48
  • $\begingroup$ 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. $\endgroup$ – SKL Sep 24 '16 at 4:54
  • $\begingroup$ 15=12+3, 16=13+3, 16=14+3, etc. $\endgroup$ – vadim123 Sep 24 '16 at 4:56
  • 1
    $\begingroup$ 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. $\endgroup$ – dxiv Sep 24 '16 at 7:06
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.