Results 1 to 5 of 5

Math Help - Induction proof

  1. #1
    Senior Member DivideBy0's Avatar
    Joined
    Mar 2007
    From
    Melbourne, Australia
    Posts
    432

    Induction proof

    Exercise 2.9. Prove that if n ≥ 12 then n can be written as a sum of 4ís and 5ís. For example, 23 = 5 + 5 + 5 + 4 + 4 = 3 ∑ 5 + 2 ∑ 4. [Hint. In this case it will help to do the cases n = 12, 13, 14, and 15 separately. Then use induction to handle n ≥ 16.]

    It's not too hard to provide cases for n = 12, 13, 14, 15, but the second bit is hard:
    If n = 5a + 4b, then n + 1 = 5c + 4d?
    Any tips on how to get started? I think I'm introducing too many variables, but I duno really :/
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by DivideBy0 View Post
    Exercise 2.9. Prove that if n ≥ 12 then n can be written as a sum of 4ís and 5ís. For example, 23 = 5 + 5 + 5 + 4 + 4 = 3 ∑ 5 + 2 ∑ 4. [Hint. In this case it will help to do the cases n = 12, 13, 14, and 15 separately. Then use induction to handle n ≥ 16.]

    It's not too hard to provide cases for n = 12, 13, 14, 15, but the second bit is hard:
    If n = 5a + 4b, then n + 1 = 5c + 4d?
    Any tips on how to get started? I think I'm introducing too many variables, but I duno really :/
    Well if n>=16, then you have one of the following cases:

    1. 3x5 + some more 4's and 5's
    2. 2x5 + 1x4 + other 4's
    3. 1x5 + 1x4's + more 4's
    4. 0x5 + 4x4's + more 4's

    In the first case trade in 3x5's for 4x4's to reach n+1.
    In the second case trade in 1x5 and 1x4 for 2x5's to reach n=1
    In third case trade in 1x5 and 1x4 for 2x5's to reach n+1
    In fourth case trade in 1x4 for 1x5 to reach n+1

    RonL
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    If a and b are relatively prime then eventually ever number can be expressed as their sum.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member DivideBy0's Avatar
    Joined
    Mar 2007
    From
    Melbourne, Australia
    Posts
    432
    Thanks, so I have to do induction on the three cases separately?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by DivideBy0 View Post
    Thanks, so I have to do induction on the three cases separately?
    No what you do is assume that the proposition is true for some k, and
    observe that for this k one of the four cases applies (you don't know which),
    but whichever it is the explanation in the earlier post means the proposition
    is true for k+1.

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 11th 2011, 07:22 AM
  2. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 16th 2010, 12:09 PM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  4. Proof by Induction??
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 6th 2008, 03:55 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM

Search Tags


/mathhelpforum @mathhelpforum