Results 1 to 5 of 5

Thread: 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 $\displaystyle P(n)$ is the propositional function:
    $\displaystyle n = 3p + 5q$, where $\displaystyle n, p, q \in \mathbb{N}_0$ (i.e. non-negative integers)
    Then we need to show that $\displaystyle P(n) \Rightarrow P(n+1)$ and $\displaystyle P(n+2)$. $\displaystyle P(n+3)$ is self-evident since we may replace $\displaystyle p$ by $\displaystyle (p+1)$; hence we will then have shown that $\displaystyle P(n)\Rightarrow P(n+i)$ for all $\displaystyle i \ge 1$.

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

    $\displaystyle = 3(p+2) + 5(q-1)$

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

    Now $\displaystyle P(8)$ states:
    $\displaystyle 8 = 3p+5q$
    which is true when $\displaystyle p = 1$ and $\displaystyle q = 1$, and thus the conditions on $\displaystyle p$ and $\displaystyle q$ are satisfied for $\displaystyle n = 8$. Hence, by Induction, $\displaystyle P(n)$ is true for all $\displaystyle 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 $\displaystyle 1$ to both sides of the equation.

    If
    $\displaystyle n = 3p + 5q$
    then
    $\displaystyle n+1 = 3p+5q+1$
    The reason I've added $\displaystyle 1$ to both sides is that I wanted to set up an expression that would enable me to show that $\displaystyle P(n) \Rightarrow P(n+1)$; in other words, to show that if we can express the sum $\displaystyle n$ cents using $\displaystyle 3$'s and $\displaystyle 5$'s then we can express $\displaystyle (n+1)$ using $\displaystyle 3$'s and $\displaystyle 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: Jul 24th 2011, 02:33 PM
  2. Mathematical Induction Proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Aug 28th 2010, 07:10 AM
  3. mathematical induction proof
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Jan 27th 2010, 12:35 PM
  4. Proof by mathematical Induction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Apr 20th 2009, 07:33 AM
  5. Proof Of Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: Mar 19th 2007, 08:24 PM

Search Tags


/mathhelpforum @mathhelpforum