Results 1 to 2 of 2

Thread: Induction proof.....

  1. #1
    Newbie
    Joined
    Jun 2016
    From
    london
    Posts
    16

    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 ?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Oct 2009
    From
    Brisbane
    Posts
    895
    Thanks
    200

    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)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by induction A u B = A + B - A n B
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Oct 19th 2011, 07:19 PM
  2. Another Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 15th 2011, 07:26 PM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Mar 8th 2009, 10:33 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: Jun 8th 2008, 02:20 PM
  5. Induction Proof again :(
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Nov 21st 2007, 08:17 AM

/mathhelpforum @mathhelpforum