Results 1 to 5 of 5

Math Help - Proof using mathematical induction

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    9

    Proof using mathematical induction

    Show that any postage greater than or equal to 8 cents can be made from 3 cent and/or 5 cent stamps using mathematical induction. For example, 31 cents can be made by using five 5 cent stamps and two 3 cent stamps for a total of 25+6=31 cents.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jun 2009
    Posts
    806
    Thanks
    4
    Quote Originally Posted by kullgirl418 View Post
    Show that any postage greater than or equal to 8 cents can be made from 3 cent and/or 5 cent stamps using mathematical induction. For example, 31 cents can be made by using five 5 cent stamps and two 3 cent stamps for a total of 25+6=31 cents.
    If n is the total cents, it can be written as
    n = 5*x + 3*y
    If you replace x and y by (x+1) and (y+1), then
    n' = 5*(x+1) + 3*(y+1) = 5x + 3y + 5 + 3 = n + 8.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1
    Hello kullgirl418
    Quote Originally Posted by kullgirl418 View Post
    Show that any postage greater than or equal to 8 cents can be made from 3 cent and/or 5 cent stamps using mathematical induction. For example, 31 cents can be made by using five 5 cent stamps and two 3 cent stamps for a total of 25+6=31 cents.
    Suppose that P(n) is the propositional function:
    n = 3p + 5q, where n, p, q \in \mathbb{N}_0 (i.e. non-negative integers)
    Then we need to show that P(n) \Rightarrow P(n+1) and P(n+2). P(n+3) is self-evident since we may replace p by (p+1); hence we will then have shown that P(n)\Rightarrow P(n+i) for all i \ge 1.

    So P(n) \Rightarrow
    n+1 = 3p+5q+1
    =3p+6 +5q-5

    = 3(p+2) + 5(q-1)

    \Rightarrow P(n+1), provided q \ge 1
    and:
    n+2 = 3p + 5q+2
    = 3(p-1) + 5(q+1)
    \Rightarrow P(n+2), provided p \ge 1
    Hence, provided p \ge 1 and q \ge 1,\; P(n) \Rightarrow P(n+1) and P(n+2).

    Now P(8) states:
    8 = 3p+5q
    which is true when p = 1 and q = 1, and thus the conditions on p and q are satisfied for n = 8. Hence, by Induction, P(n) is true for all n \ge 8.

    Grandad
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Oct 2009
    Posts
    9
    i don't get how n+1=3q+5p+1
    i don't get where the one comes from on the right side
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1
    Hello kullgirl418
    Quote Originally Posted by kullgirl418 View Post
    i don't get how n+1=3q+5p+1
    i don't get where the one comes from on the right side
    Sorry, I don't really understand where the problem is. I've simply added 1 to both sides of the equation.

    If
    n = 3p + 5q
    then
    n+1 = 3p+5q+1
    The reason I've added 1 to both sides is that I wanted to set up an expression that would enable me to show that P(n) \Rightarrow P(n+1); in other words, to show that if we can express the sum n cents using 3's and 5's then we can express (n+1) using 3's and 5's.

    This, after all, is what induction is all about.

    Grandad
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 24th 2011, 02:33 PM
  2. Mathematical Induction Proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 28th 2010, 07:10 AM
  3. mathematical induction proof
    Posted in the Algebra Forum
    Replies: 2
    Last Post: January 27th 2010, 12:35 PM
  4. Proof by mathematical Induction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 20th 2009, 07:33 AM
  5. Proof Of Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: March 19th 2007, 08:24 PM

Search Tags


/mathhelpforum @mathhelpforum