# Thread: Induction proof.....

1. ## Induction proof.....

Hello guys

Big day today. Been thinking for some hours on this . Getting quite tired nearly to sleep . Again, really really kind of your help I will look other problems but for not so easy me .

PROBLEM

If $n\geq8$ show that any postage of $n$ cents can be made exactly usng only 3-cent & 5-cent stamps.

SOLUTION

The solution gives 2 rules and assert that for $k\geq8$ "1 of these cases must occur "

Rule 1. One or more 5-cent stamps are used to make up $k$ cents postage.
Replace 1 of them with $2$ 3-cent stamps to make $k+1$ cents postage

Rule 2. Three or more 3-cent stamps are used to make up $k$ cents postage.
Replace 3 of them with $2$ 5-cent stamps to make $k+1$ cents postage.

~~~~~~

$k=8 \Rightarrow$ 3-cent, 5cent
$k=9 \Rightarrow$ only 3-cent
$k=10 \Rightarrow$ only 5-cent
$k=11 \Rightarrow$ k+1 with Rule 1
$k=12 \Rightarrow$ only 3-cent
$k=13 \Rightarrow$ k+1 with Rule 2
$k=14 \Rightarrow$ ????

QUESTION

so consider $k=14$

We have the case $14=5+9$ where we replace $2$ 5-cent with $3$ 3-cent. This is not either Rule 1 (replace $1$ 5 cent with $2$ 3-cent) or Rule 2 (replace $3$ 3-cent with $2$ 5-cent) . So maybe we need Rule 3.

Rule 3. Three or more 5-cent stamps are used to make $k+1$ cents postage.
Replace 2 of them with $3$ 3-cent stamps to make $k$ cents postage

Or maybe Rule 3 in Rule 1 or Rule 2 ?

2. ## Re: Induction proof.....

k=13 = 5+5+3

Apply
Rule 1. One or more 5-cent stamps are used to make up k cents postage.
Replace 1 of them with 2 3-cent stamps to make k+1 cents postage

ie replace 1 of the 5cent stamps with 2 3 cents stamps

So
14 = (3+3) + 5 +3 where the first 5c that was used to make up 13 is replaced with 2 3c stamps. (basically you are swapping 5c for 6c which causes an increment of 1)