1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Proof by induction

  1. May 9, 2010 #1
    Use the method of induction to prove that if a ∈ Z is a prime
    integer and if a/b1b2...br then a/bi for some 1 ≤ i ≤ r

    I could prove this in other ways but how do you do this by induction?

    I'm only use to induction of the form 'assume true for n show (n+1) also holds true'

    Could someone start me of? Thanks
     
  2. jcsd
  3. May 9, 2010 #2

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Hi Firepanda! :smile:

    Start "assume it's true for r ≤ n", and then try to prove it for r = n+1. :wink:
     
  4. May 9, 2010 #3
    ok so..

    a/b1b2...br then a/bi for some 1 ≤ i ≤ r

    assume true for r ≤ n

    a/b1b2...bn then a/bi for some 1 ≤ i ≤ n

    if r = n+1

    a/b1b2...bnbn+1 then a/bi for some 1 ≤ i ≤ n+1

    but since we already had 1 ≤ i ≤ n then surely this is true?

    Probably wrong
     
  5. May 9, 2010 #4

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    No, if a divides a product of n+1 numbers, how can a theorem about products of n numbers be applied? :confused:
     
  6. May 9, 2010 #5

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Work backwards. There are three cases:
    • a|b1 and a|b2b3...br (game over), or
    • a|b1 (game over), or
    • a|b2b3...br.
    In the last case, recurse.

    I don't think tiny-tim's idea will work because there is no base case to make the stack of dominos fall.
     
  7. May 9, 2010 #6
    if a|bc and gcd(a,b) = 1 since a is prime and b certainly isn't as its a product

    then a|c, so since a|c then a|bn+1, and 1 ≤ i ≤ n+1 so this holds true?

    ^ sorry this is wrong gcd(a,b) isnt 1 its bi

    im stumped
     
  8. May 9, 2010 #7

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Conceptually, there are four cases:
    1. a divides b1 and b2b3...br.
    2. a divides b1 but not b2b3...br.
    3. a divides b2b3...br but not b1
    4. a divides neither b1 nor b2b3...br.
    You need to show that these are the only four cases, and that case (4) does not apply.
     
  9. May 9, 2010 #8

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    I was thinking of saying a|bbn+1 where b = b1…bn :wink:
     
  10. May 9, 2010 #9

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    So what is the base case? You do not know that a|b1.

    You have proved that if a|b2b3...br then a|b2b3...brbr+1. The OP needs to prove the converse (assuming a does not divide br+1; it's game over if a|br+1).
     
  11. May 9, 2010 #10

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    No, if a|bbn+1, then … :wink:
     
  12. May 9, 2010 #11
    go on... wanna see how you've done it!
     
  13. May 9, 2010 #12

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Apply the induction … a divides the product of two numbers, so … ?
     
  14. May 9, 2010 #13
    a|b or a|bn+1?
     
  15. May 9, 2010 #14

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    That's right. :smile:

    Now carry on … ​
     
  16. May 9, 2010 #15
    dont we just conclude that i is certainly contained between 1 and n+1 inclusive so the induction hypothesis is true?
     
  17. May 9, 2010 #16

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    "i is certainly contained …"

    That's meaningless!

    What are you talking about? What is i?

    (You're trying to find an i ≤ 1+1 such that a|bi, you haven't been given an i)
     
  18. May 9, 2010 #17
    but we assumed it was true?

    ok then but we've shown a must divide one of the terms so a can divide at least one of the i ≤ n+1
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook