Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Mathematical Induction help needed

  1. Oct 4, 2004 #1
    i was having trouble coming up with an induction proof for this problem, although i have tried and was able to prove it sumhow(using numbers 1 n so forth, teacher doesn't allow us to use them yet), but not using induction. I have no clue on how to do this using induction. plz help me.

    Problem: Prove that for all n>=12, there are non-negative integers a and b such that n=7a+3b.

    THen note that if a,b are integers such that 7a+3b>=12, then a>=2 and b>=2.

    Then put the above property so that having the expression n of the type (n=7a+3b) gives an expression for n+1 also for the type (n=7a+3b).

    how am i suppose to start this proof, using induction and using facts if needed.
  2. jcsd
  3. Oct 4, 2004 #2


    User Avatar
    Science Advisor
    Homework Helper

    Assume it's true for n. Then for n+1

    [tex]n+1 = 7a'+3b'[/tex]

    so that

    [tex]n = 7a'+3b'-1 = 7a' + 3 b' + 6 - 7 = 7(a'-1) + 3(b'+2)[/tex]

    Just set a' - 1 = a and b' +2 = b and you have your proof.
  4. Oct 4, 2004 #3
    aaaah, now i understand.. thanx alot, i didn't bother going any further after writing n+1=7a+3b. i really really appreciate the help, thanx again
  5. Oct 5, 2004 #4


    User Avatar
    Science Advisor

    Isn't there a crucial step in induction missing? What happens when n= 12?
  6. Oct 5, 2004 #5
    aren't we suppose to assume it is true for the first number, for example n=12, and then prove for the next number n+1.
  7. Oct 5, 2004 #6
    Yes, it must first be proven that the statement is true for 12, then go on to show it is true for n+1
  8. Oct 5, 2004 #7
    so how do we prove it for 12, if we dont know a and b?
  9. Oct 5, 2004 #8
    firstly you said a => 2 and b => 2 for n => 12

    7(2) + 3(2) = 14 + 6 = 20 => 12 and this is true for the first allowed case for 12 since 20 => 12, the last time i checked

    thats your first step

    then assume it for k and follow the steps given to you before me
  10. Oct 5, 2004 #9


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Matrix, can you not find a, b by simple trial and error ? It hardly takes a couple of tries before you find the right values.

    Stunner, you are not answering matrix's question about the initial case.
    Last edited: Oct 5, 2004
  11. Oct 5, 2004 #10

    Tom Mattson

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    It looks to me like you don't have a feel for the induction process yet.

    Just to elaborate one what Spectre said, you have to prove that the statement P(n) is true for n=12. In fact, if you don't do that, you will only prove the conditional statement: If P(n) is true, then P(n+1) is true.

    Well what if P(n) is not true?

    That's why both steps are needed. When both P(12) and P(n)-->P(n+1) are proven, then the proof holds for all n>=12 by the domino effect.

    P(12) is true. proven directly
    P(12)-->P(13) because P(12)-->P(12+1), and P(12) is true
    P(13)-->P(14) because P(13)-->P(13+1), and P(13) is true

    and so on.
  12. Oct 5, 2004 #11
    If P(n) is not true, then P(n+1) is true. p(n)=>p(n+1) then P(n) must be true, according to the truth table
  13. Oct 5, 2004 #12
    beeeeeeeeeeeep ..........
    check the truth table again .....
    given a statement p->q
    if p is false and q is true, p->q is still true

    so given the truth values of q and p->q , one cannot determine the truth value of p. If that were so , most of the modus ponen rules i study in AI would come to nought!!! really!!

    -- AI
    P.S-> 7*0+3*4 = 12
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook