Results are out! Find what you need...fast. Get quick advice or join the chat
Hey! Sign in to get help with your study questionsNew here? Join for free to post

Proof By Induction for Divisibility Help Needed

Announcements Posted on
Become part of the Welcome Squad! Apply here! 28-10-2014
    • Thread Starter
    • 0 followers
    Offline

    ReputationRep:
    (Original post by Matureb)
    No. In this case 30 is divisible by 2 and by 6. But not by 18. For 18 you would need to show it was divisible by 2 and 9.
    Ugh I am confused over tiny technical details..
    So to prove something is divisible by 30, it would be 15 and 2 ?
    for 18 - 2 and 9
    for x - any two factors which multiply to give x ?

    Or is it that one of the factors must always be 2 ?
    eg to prove something is divisible by 60 can I use 10 and 6 or must I use 2 and 30, or will 4 and 15 also work ?
    • 3 followers
    Offline

    ReputationRep:
    (Original post by member910132)
    Oh, can we say that at least one of those numbers must be even and so the whole thing can be divided by 2 and so the whole number is even.

    But can someone clarify this issue of using factors to prove something is divisible by a number ?
    If I wanted to prove something is divisible by x, then obviously proving it is divisible by Ax would suffice right ? (where A is a constant integer).

    But if I am to prove that something is divisible by 12 for example then must I say that it is divisible by 2 of it's factors, eg show that it is divisible by both 3 and 4 or 2 and 6 ?

    Thnx tons
    In general if you want to prove x is divisible by y then you have to show x is divisible by each of the prime factors of y.
    • Thread Starter
    • 0 followers
    Offline

    ReputationRep:
    (Original post by miml)
    In general if you want to prove x is divisible by y then you have to show x is divisible by each of the prime factors of y.
    Tank you so much for this !!!!!!!!!!
    • 0 followers
    Online

    ReputationRep:
    60 = 2*2*3*5. To test if a nunber is divisible by 60 it must be divisible by (2*2), by 3 and by 5. I.e it must be divisible by 3, 4 and 5. Note, these are relatively prime.
    You are right that 4 and 15 will do since if it is divisible by 15, then it is automatically divisible by 3 and 5.
    10 and 6 would not do. 90 is divisible by 10 and 6 , but not by 60.
    • 0 followers
    Offline

    ReputationRep:
    Surely it would be easier to say

    1) when n=k
    assume n^3-n is divisible by 6

    2) when n=k+1
    n^3+3n^2+2n

    1)x4 + 2)x2 gives 4n^3-4n + 2n^3+6n^2+4n = 6n^3+6n^2 = 6(n^3+n^2)
    ......................(divisible by 6).............................. .................(divisible by 6)

    As the two bits I've shown are divisible by 6, the 6n^2+4n must be divisible by 6 and so is the equation in 2).
    • Thread Starter
    • 0 followers
    Offline

    ReputationRep:
    (Original post by Matureb)
    60 = 2*2*3*5. To test if a nunber is divisible by 60 it must be divisible by (2*2), by 3 and by 5. I.e it must be divisible by 3, 4 and 5. Note, these are relatively prime.
    You are right that 4 and 15 will do since if it is divisible by 15, then it is automatically divisible by 3 and 5.
    10 and 6 would not do. 90 is divisible by 10 and 6 , but not by 60.
    Got it, great ! So I just need to shwo that it is divisible by it's prime factors or the prime factors multiplied by each other (in the example of 2.2.3.5 = 4.15)

    (Original post by Quip)
    Surely it would be easier to say

    1) when n=k
    assume n^3-n is divisible by 6

    2) when n=k+1
    n^3+3n^2+2n

    1)x4 + 2)x2 gives 4n^3-4n + 2n^3+6n^2+4n = 6n^3+6n^2 = 6(n^3+n^2)
    ......................(divisible by 6).............................. .................(divisible by 6)

    As the two bits I've shown are divisible by 6, the 6n^2+4n must be divisible by 6 and so is the equation in 2).
    Sorry I can't follow what you have done at all, but it is okay, I get it now. And I realize that their are other ways of doing it but I wanted to know how to do it in a specific way.
    • 3 followers
    Offline

    ReputationRep:
    (Original post by Quip)
    Surely it would be easier to say

    1) when n=k
    assume n^3-n is divisible by 6

    2) when n=k+1
    n^3+3n^2+2n

    1)x4 + 2)x2 gives 4n^3-4n + 2n^3+6n^2+4n = 6n^3+6n^2 = 6(n^3+n^2)
    ......................(divisible by 6).............................. .................(divisible by 6)

    As the two bits I've shown are divisible by 6, the 6n^2+4n must be divisible by 6 and so is the equation in 2).
    Might be missing something, but your argument only shows that the "equation 2" is divisible by 2?

    Surely you want 2n^3 + 6n^2 + 4n to be divisible by 12, to show that our original expression is divisible by 6.
    • 0 followers
    Offline

    ReputationRep:
    (Original post by miml)
    Might be missing something, but your argument only shows that the "equation 2" is divisible by 2?

    Surely you want 2n^3 + 6n^2 + 4n to be divisible by 12, to show that our original expression is divisible by 6.
    I thought that because it equals something that is divisible by 6 and equation 1 is divisible by 6 (assumed), the 2n^3 + 6n^2 + 4n must also be divisible by 6. (If two things are added which are both divisible by 6, the sum will also be divisible by 6)

    However, I've just realised that as I've already multiplied it by 2, this only shows that n^3 + 3n^2 + 2n is divisible by 3 and you're right I need to show 2n^3 + 6n^2 + 4n is divisible by 12. Sorry, my mistake (I've been on holiday too long and forgotten how to do maths)
    • 1 follower
    Offline

    ReputationRep:
    there are different cases to consider:

    firstly, n^3-n can be expressed as: n(n-1)(n+1)

    so, first, if n is divisible by 3, then n-1 is divisible by2, so whole thing divisible by 6 - nothing further needed there.

    second thing you do is examine what happens when n is both odd and even: odd n=2k+1 for some k in Z - you find out, by factoring, that both expressions are divisible by 2,

    3rd, you examine n when it`s NOT divisible by 3 - by using in the expression, (then factoring it) both n=3k+1, and n=3k-1 (this ensures thatyou encompass every number NOT divisible by 3) - you find that the expression n^3-1 when used with these values, simplifies to something with a factor of 3,

    so you will have proved simultaneously that the expression has factors of both 2 and 3...
    • 14 followers
    Offline

    ReputationRep:
    (Original post by Hasufel)
    there are different cases to consider:

    firstly, n^3-n can be expressed as: n(n-1)(n+1)

    so, first, if n is divisible by 3, then n-1 is divisible by2, so whole thing divisible by 6 - nothing further needed there.

    second thing you do is examine what happens when n is both odd and even: odd n=2k+1 for some k in Z - you find out, by factoring, that both expressions are divisible by 2,

    3rd, you examine n when it`s NOT divisible by 3 - by using in the expression, (then factoring it) both n=3k+1, and n=3k-1 (this ensures thatyou encompass every number NOT divisible by 3) - you find that the expression n^3-1 when used with these values, simplifies to something with a factor of 3,

    so you will have proved simultaneously that the expression has factors of both 2 and 3...
    Problem with this is proof was asked to be done by induction.

    To prove by induction that a number is divisible by some number, the difference between k and k+1 must be used. Otherwise its just a direct proof.

    (Original post by BJack)
    .
    Also a problem with your idea of just showing either number is a multiple of 6 is that it isn't induction. You can do all the induction steps to disguise it as induction, but unless you actually use the assumption that n³ - n is a multiple of 6 then its just a direct proof.
    • 3 followers
    Offline

    ReputationRep:
    How I would have done it, if it had to be done by induction:
    Assume true for n=k then  k^3 - k is divisible by 6.

    For n=k+1  (k+1)^3 - (k+1) = k^3 + 3k^2 + 3k + 1 - k - 1 = k^3 + 3k^2 +2k = (k^3 - k) + (3k^2 - 3k)

    The first bracket is divisible by 6 by our assumption so it remains to show the second bracket is.  3k^2 - 3k = 3k(k+1)
    Which is clearly divisible by 3, and as it contains a product of two consecutive numbers i.e. one must be even, it is also divisible by 2. Hence divisible by 6 and we have shown that for n=k+1 the expression is divisible by 6.

    If it didn't have to be done by induction
    Spoiler:
    Show
    n^3 - n = (n-1)n(n+1) which is the product of 3 consecutive integers, hence is divisible by 3 and 2
    • 8 followers
    Offline

    ReputationRep:
    (Original post by hassi94)
    Also a problem with your idea of just showing either number is a multiple of 6 is that it isn't induction. You can do all the induction steps to disguise it as induction, but unless you actually use the assumption that n³ - n is a multiple of 6 then its just a direct proof.
    Oh dear.

Reply

Submit reply

Register

Thanks for posting! You just need to create an account in order to submit the post
  1. this can't be left blank
    that username has been taken, please choose another Forgotten your password?
  2. this can't be left blank
    this email is already registered. Forgotten your password?
  3. this can't be left blank

    6 characters or longer with both numbers and letters is safer

  4. this can't be left empty
    your full birthday is required
  1. By joining you agree to our Ts and Cs, privacy policy and site rules

  2. Slide to join now Processing…

Updated: April 17, 2012
New on TSR

Halloween 2014

Join the TSR Halloween party...if you dare!

Article updates
Reputation gems:
You get these gems as you gain rep from other members for making good contributions and giving helpful advice.