Results 1 to 3 of 3
Like Tree1Thanks
  • 1 Post By emakarov

Math Help - Postage stamp problem: Weak versus Strong Induction

  1. #1
    Member
    Joined
    Nov 2009
    Posts
    80

    Postage stamp problem: Weak versus Strong Induction

    I am instructed to prove that postage amounts greater than or equal to 54 can be taken care of using solely 7 and 10 cent stamps. The book asks me to use strong induction.

    My Basis is:

    54 = 4*10 + 2*7

    My inductive step is:

    (assume n = 10*j + 7*k for some n >= 54 and j,k are integers)

    n + 1 = 10(j - 2) + 7(k + 3)


    So the inductive step infers (as far as I can see) that if the hypothesis is true for n, it is true for n + 1. The basis is shown to be true.

    It seems to me that this concludes a proof by WEAK induction, but the solutions manual presents a nearly identical argument and calls it strong induction.

    Please help
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,501
    Thanks
    765

    Re: Postage stamp problem: Weak versus Strong Induction

    Quote Originally Posted by jmedsy View Post
    My inductive step is:

    (assume n = 10*j + 7*k for some n >= 54 and j,k are integers)

    n + 1 = 10(j - 2) + 7(k + 3)
    It is important that the induction hypothesis says n = 10*j + 7*k for some n >= 54 and nonnegative integers j, k. Then j - 2 is not necessarily a nonnegative integer, so you have not proved that n is represented in a required way.

    There are two options. One is to consider the cases j = 0 and j = 1 separately. This would still be a proof by regular induction. Another is to prove P(n) -> P(n + 7) where P is the induction hypothesis above. The induction step is obvious, but you need strong induction (though, strictly speaking, you use only P(n) and not P(k) for all 54 <= k < n + 7 in the proof of P(n + 7)). You also need to prove 7 bases cases.

    See also this tread.
    Thanks from jmedsy
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2009
    Posts
    80

    Re: Postage stamp problem: Weak versus Strong Induction

    Quote Originally Posted by emakarov View Post
    It is important that the induction hypothesis says n = 10*j + 7*k for some n >= 54 and nonnegative integers j, k. Then j - 2 is not necessarily a nonnegative integer, so you have not proved that n is represented in a required way.

    There are two options. One is to consider the cases j = 0 and j = 1 separately. This would still be a proof by regular induction. Another is to prove P(n) -> P(n + 7) where P is the induction hypothesis above. The induction step is obvious, but you need strong induction (though, strictly speaking, you use only P(n) and not P(k) for all 54 <= k < n + 7 in the proof of P(n + 7)). You also need to prove 7 bases cases.

    See also this tread.
    This is correct.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] some problem in strong induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 6th 2011, 07:05 PM
  2. Postage Stamp Problem - Maximum amount of stamps
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 1st 2010, 12:53 AM
  3. Induction for postage stamps
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: May 6th 2010, 02:57 AM
  4. Hash values: Weak and strong collision resistance
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: December 6th 2008, 06:14 AM
  5. Strong Induction Problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 31st 2008, 05:09 AM

Search Tags


/mathhelpforum @mathhelpforum