Results 1 to 7 of 7

Math Help - proof by induction

  1. #1
    Super Member
    Joined
    Oct 2007
    From
    Santiago
    Posts
    517

    proof by induction

    hey guys need help solving this question.
    Use induction to prove that every positive integer \geq 24 can be written as the sum of 5's and 7's. Not sure how to proceed with this question. Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by jvignacio View Post
    hey guys need help solving this question.
    Use induction to prove that every positive integer \geq 24 can be written as the sum of 5's and 7's. Not sure how to proceed with this question. Thanks!

    24=2(7+5)

    25=2\cdot 5=5+5

    26=3\cdot 7 +5

    27=7+4\cdot 5

    28=4\cdot 7

    And the above suffices to show the claim (why?)

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2010
    Posts
    5
    Quote Originally Posted by tonio View Post
    24=2(7+5)

    25=2\cdot 5=5+5

    26=3\cdot 7 +5

    27=7+4\cdot 5

    28=4\cdot 7

    And the above suffices to show the claim (why?)

    Tonio
    What Tonio has done is prove your base case (you will need strong induction for this).

    For the inductive hypothesis, let n \geq 28 and suppose that your claim holds for all  k \leq n

    You want to prove that n+1 can be expressed as a sum of 5's and 7's.

    Consider  n+1-5 What can you say about it?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Oct 2007
    From
    Santiago
    Posts
    517
    Quote Originally Posted by Yasen View Post
    What Tonio has done is prove your base case (you will need strong induction for this).

    For the inductive hypothesis, let n \geq 28 and suppose that your claim holds for all  k \leq n

    You want to prove that n+1 can be expressed as a sum of 5's and 7's.

    Consider  n+1-5 What can you say about it?
    Shouldnt it be n \geq 24 ? I understand the base case not sure what you mean by n+1-5
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Mar 2010
    Posts
    5
    Quote Originally Posted by jvignacio View Post
    Shouldnt it be n \geq 24 ? I understand the base case not sure what you mean by n+1-5
    Tonio proved your statement holds for 24, 25, 26, 27, and 28. So what you need to do is prove it holds for all numbers greater than 28 (and as it holds for 24-28, these two together show your statement holds for all numbers greater than 24).

    Do you know how to do strong induction? For it, you suppose that a statement P holds. Then, if (P(0) holds and (whenever P(k) holds for all  k \leq n , then P(n+1) holds)), then P holds for all natural numbers.

    In your case, we are amending this principle a little:

    1. Instead of P(0), you have P(24)-P(28) (where P is the statement that the integer can be written as the sum of 5's and 7's).

    2. In the assumption of the IH, instead of saying P(k) holds for all k<=n, we way it holds for all  24 \leq k \leq n (i.e. we remove the first couple of numbers)

    3. As we have shown P(24)-P(28), all we need to do is "start" the inductive hypothesis from P(29) on - i.e., assume n is greater or equal to 28, and that P(k) holds for all  24 \leq k \leq n . We want to show that P(n+1) holds.


    If we can do this, then this principle would show us that (the following is an intuitive discourse):

    from P(28) holds: apply IH with n=28, and get that P(29) holds.
    from P(29) holds: apply IH with n=29, and get that P(30) holds,... etc. Hence it holds for all natural numbers greater than 28, and as we've shown it holds for 24-28, it holds for all greater than 24.

    (end of discourse)

    So, how do we do (2)?

    We have assumed  n \geq 28 and that (IH) the statement holds for all  24 \leq k \leq n . How do we show that P(n+1) holds?

    Consider n+1-5=n-4. As  n-4 \leq n , what does our inductive hypothesis tell us about n-4? And what can we conclude about (n-4)+5=n+1?

    This would conclude the induction, hence concluding the proof.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Mar 2010
    Posts
    2
    hey, i was trying to find an answer to this exact question, i have just started a course in discrete mathematics and are lecturers are pretty bad and don't really explain things well, we have been given this question in our first assignment and while i understand how to get the answer, i dont know how to properly set it out, i have never done strong induction before, so would you be able to write out the structure of teh answer to this quesiton, thanks
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Mar 2010
    Posts
    2
    It would be a far more productive use of your time to actually sit down with your textbook and practice some of the examples (I suggest pp291-294). I somehow doubt that you'll be allowed forum access during the final exam. It would also be helpful to understand that you're studying a quite challenging topic; blaming the lecturers for your inability to understand is not going to help. If you're really having trouble, there are a variety of resources at your disposal. Speak to your tutors or visit the Nemeracy Centre.

    Accept that you've been given a massive clue here, and move along. Begging for answers smacks of desperation.

    PS, you've left your run a little late, haven't you? It's due in tomorrow.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by induction
    Posted in the Algebra Forum
    Replies: 13
    Last Post: January 31st 2011, 05:41 PM
  2. an induction proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 5th 2009, 02:31 PM
  3. proof by induction ...
    Posted in the Calculus Forum
    Replies: 2
    Last Post: August 8th 2009, 03:07 PM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 10:33 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 02:20 PM

Search Tags


/mathhelpforum @mathhelpforum