Results 1 to 3 of 3

Math Help - Strong induction

  1. #1
    Junior Member
    Joined
    Sep 2008
    Posts
    37

    Strong induction

    Suppose that a store offers gift certificates in denominations of 25 dollars and 40 dollars. Determine the possible total amounts that you can form using these gift certificates. Prove your answer using strong induction.

    Im stuck on this question, any help would be appreciated.

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Sep 2008
    Posts
    37
    Would this be on the right track?

    $25,$40,$50,$75,$80,$100,$120,$125

    25x1=25
    40x1=40
    25x2=50
    25x3=75
    40x2=80
    25x4=100
    40x3=120
    25x5=125
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Continuing the previous comment, you can also get

    65 = 40 + 25,
    90 = 40 + 225,
    105 = 240 + 25,
    130 = 240 + 225.

    You can't get 135, but you can get 140, 145, 150, 155 and 160. Then at that stage the strong induction kicks in (everything up until that point is just the base case). The inductive hypothesis is that you can get all the totals listed so far, together with all multiples of 5 above 160.

    The inductive step works because we already have a run of five consecutive multiples of 5 (140, 145, 150, 155 and 160). If n is any multiple of 5 that is greater than 160, then the inductive hypothesis tells you that n-25 is a possible total, from which it obviously follows that n is (by adding one extra $25 certificate).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 01:36 AM
  2. Strong induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 26th 2010, 02:10 PM
  3. STRONG induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 6th 2009, 09:23 PM
  4. Strong Induction help
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 7th 2009, 09:48 PM
  5. Strong Induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 5th 2008, 09:50 AM

Search Tags


/mathhelpforum @mathhelpforum