Hey there Sign in to join this conversationNew here? Join for free

Proof By Induction for Divisibility Help Needed

Announcements Posted on
Study Help needs new mods! 14-04-2014
We're up for a Webby! Vote TSR to help us win. 10-04-2014
    • Thread Starter
    • 0 followers
    Offline

    ReputationRep:
    Prove by induction that n^3 - n is divisible by 6.

    Would I get full marks if I have done this:

    let u_n = n^3 - n and assume it is divisible by 6.

    Therefor, u_{n+1} = n^3 + 3n^2 + 2n

    Thus, u_{n+1} - u_n = 3n^2 + 3n

    As we assumed u_n was divisible by 6 and clearly 3n^2 + 3n is divisible by 6 (as 3 is a factor of 6) then this proves that u_{n+1} is divisible by 6.

    For n=1 we have 1-1=0, which is divisible by 6.

    I am not 100% sure on the part where I use the factor of 3 to show that it is divisible by 6, I couldn't get a 6 or a multiple of 6.
    I would highly appreciate it if people could give me the general rule about if it is okay to use factors of the number we are trying to show it is divisible by and not the number itself or a multiple.
    I am also unsure about the end where I say 0 is divisible by 6, is 0 a positive integer ?

    Edit: I would highly appreciate some general advice about what to do after getting U(n) and U(n+1), I struggle to work out whether to add them, subtract them, add one to a multiple of another (which multiples can we use ?), can we multiply both U(n) and U(n+1) but different multiples......


    Thnx
    • 32 followers
    Offline

    ReputationRep:
    (Original post by member910132)
    Prove by induction that n^3 - n is divisible by 6.

    Would I get full marks if I have done this:

    let u_n = n^3 - n and assume it is divisible by 6.

    Therefor, u_{n+1} = n^3 + 3n^2 + 2n

    Thus, u_{n+1} - u_n = 3n^2 + 3n

    As we assumed u_n was divisible by 6 and clearly 3n^2 + 3n is divisible by 6 (as 3 is a factor of 6) then this proves that u_{n+1} is divisible by 6.

    For n=1 we have 1-1=0, which is divisible by 6.

    I am not 100% sure on the part where I use the factor of 3 to show that it is divisible by 6, I couldn't get a 6 or a multiple of 6.
    I would highly appreciate it if people could give me the general rule about if it is okay to use factors of the number we are trying to show it is divisible by and not the number itself or a multiple.
    I am also unsure about the end where I say 0 is divisible by 6, is 0 a positive integer ?

    Thnx
    the bold statement seems dodgy... you could say 3 is a factor of 111 so the expression must be a multiple of 111
    • Thread Starter
    • 0 followers
    Offline

    ReputationRep:
    (Original post by the bear)
    the bold statement seems dodgy... you could say 3 is a factor of 111 so the expression must be a multiple of 111
    Good point lol, so what do I do ? I am beginning to think there is a typo in the question because of that last part about n=1 being divisible by 6 ? Is 0 divisible by any number ?
    • 4 followers
    Offline

    ReputationRep:
    (Original post by member910132)
    Edit: I would highly appreciate some general advice about what to do after getting U(n) and U(n+1), I struggle to work out whether to add them, subtract them, add one to a multiple of another (which multiples can we use ?), can we multiply both U(n) and U(n+1) but different multiples......
    When doing the proof by induction, you want to say "assume true for n=k; then for n=k+1 we have ...". So you prove the ladder goes on; then you take your basis case to show the ladder has a bottom and you're done.

    So after getting that the expression for n= k+1 is k3 + 3k2 + 2k, you simply need play with it in such a way to show that it's divisible by 6.

    Spoiler:
    Show
    try factorizing it
    • 32 followers
    Offline

    ReputationRep:
    Hint: n is either odd or even...
    • 3 followers
    Offline

    ReputationRep:
    (Original post by member910132)
    Prove by induction that n^3 - n is divisible by 6.

    Would I get full marks if I have done this:

    let u_n = n^3 - n and assume it is divisible by 6.

    Therefor, u_{n+1} = n^3 + 3n^2 + 2n

    Thus, u_{n+1} - u_n = 3n^2 + 3n

    As we assumed u_n was divisible by 6 and clearly 3n^2 + 3n is divisible by 6 (as 3 is a factor of 6) then this proves that u_{n+1} is divisible by 6.

    For n=1 we have 1-1=0, which is divisible by 6.

    I am not 100% sure on the part where I use the factor of 3 to show that it is divisible by 6, I couldn't get a 6 or a multiple of 6.
    I would highly appreciate it if people could give me the general rule about if it is okay to use factors of the number we are trying to show it is divisible by and not the number itself or a multiple.
    I am also unsure about the end where I say 0 is divisible by 6, is 0 a positive integer ?

    Edit: I would highly appreciate some general advice about what to do after getting U(n) and U(n+1), I struggle to work out whether to add them, subtract them, add one to a multiple of another (which multiples can we use ?), can we multiply both U(n) and U(n+1) but different multiples......


    Thnx
    Slightly odd way of proving it (introducing the u_n I mean)

    And as the poster above pointed out the bold bit isn't enough. In this case it is true as 3n^2+3n is always even. But the key thing is you need to show that n^3-n is divisible by both 3 and 2
    • 4 followers
    Offline

    ReputationRep:
    (Original post by miml)
    In this case it is true as 3n^2+3n is always even.
    3n2 + 3n is the difference between consecutive terms n and n+1. You can conclude from this that the difference is divisible by 6; but that doesn't prove that (n3 - n) is itself divisible by 6.
    • 13 followers
    Offline

    ReputationRep:
    (Original post by BJack)
    3n2 + 3n is the difference between consecutive terms n and n+1. You can conclude from this that the difference is divisible by 6; but that doesn't prove that (n3 - n) is itself divisible by 6.
    Well you've assumed Un is divisible by 6

    And shown Un+1 - Un is divisible by 6. Therefore Un+1 = some multiple of 6 + some other multiple of 6 = multiple of 6

    So it does prove it (but as miml said the OP does need to take a factor of 3 out, then show that what's remaining is in fact even - which is simple).
    • 4 followers
    Offline

    ReputationRep:
    (Original post by hassi94)
    Well you've assumed Un is divisible by 6
    Ah, yes.
    • Thread Starter
    • 0 followers
    Offline

    ReputationRep:
    (Original post by BJack)
    When doing the proof by induction, you want to say "assume true for n=k; then for n=k+1 we have ...". So you prove the ladder goes on; then you take your basis case to show the ladder has a bottom and you're done.

    So after getting that the expression for n= k+1 is k3 + 3k2 + 2k, you simply need play with it in such a way to show that it's divisible by 6.

    Spoiler:
    Show
    try factorizing it
    n^3 + 3n^2 + 2n = n(n+1)(n+2)

    Now how do I show that this is divisible by 6 ?
    • 4 followers
    Offline

    ReputationRep:
    (Original post by member910132)
    n^3 + 3n^2 + 2n = n(n+1)(n+2)

    Now how do I show that this is divisible by 6 ?
    What can you say about the divisibility of an integer and its two successors?
    • Thread Starter
    • 0 followers
    Offline

    ReputationRep:
    (Original post by miml)
    Slightly odd way of proving it (introducing the u_n I mean)

    And as the poster above pointed out the bold bit isn't enough. In this case it is true as 3n^2+3n is always even. But the key thing is you need to show that n^3-n is divisible by both 3 and 2
    I don't fully understand why I need to show that it is divisible by 3 and 2 ?
    If I was trying to prove something is divisible by 10 would I have to do 5 and 2 ? Is it always two of the factors ?

    Secondly, how do I show 3n^2 + 3n = 3n(n+1) is divisible by 3 and 2 ? Or how do i show it is even ?

    Edit: can anyone address this thing about n=1 gives 0 and is 0 divisible by 6 (or any number) ?
    • Thread Starter
    • 0 followers
    Offline

    ReputationRep:
    (Original post by BJack)
    What can you say about the divisibility of an integer and its two successors?
    No clue, I am new to this type of maths.
    • 0 followers
    Offline

    ReputationRep:
    As has been established the difference between consecutive terms is 3n(n+1)

    If n is even then it can be written as 2p where p is an integer. Thus substitution brings 6p(2p+1) which is obviously a multiple of 6 for all p.

    If n is odd then it can be expressed as 2q-1 where q is an integer. Substitution brings 6p(2p-1) which 6 also divides.

    As when n=0 6 divides n^3-n the induction holds.

    The key fact is that consecutive integers have at least one factor of 2.
    • Thread Starter
    • 0 followers
    Offline

    ReputationRep:
    (Original post by BJack)
    What can you say about the divisibility of an integer and its two successors?
    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
    • 0 followers
    Offline

    ReputationRep:
    18 is divisible by 2 and by 6. But not by 12. Any number divisible by 6 will be divisible by 2.
    • 13 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
    Yes member you can say that, but then you'll also have to note that in 3 consecutive numbers, one of those numbers must be divisible by 3.

    However, I do prefer the method you began with (and almost finished in your original post) - it assumes less and is the standard method for these questions at A-level.

    For the other 2 questions, yes if you can show it's divisible by say 12, it's obviously divisible by 6.

    And yes you cannot say because it is divisible by 2 it must be divisible by 286 (essentially what you did in your original post), you must show it is divisible by all the factors required.
    • Thread Starter
    • 0 followers
    Offline

    ReputationRep:
    (Original post by Matureb)
    18 is divisible by 2 and by 6. But not by 12. Any number divisible by 6 will be divisible by 2.
    But to prove something is divisible by 18 is it sufficient to prove it is divisible by 2 and 6 ?
    (Original post by hassi94)
    Yes member you can say that, but then you'll also have to note that in 3 consecutive numbers, one of those numbers must be divisible by 3.

    However, I do prefer the method you began with (and almost finished in your original post) - it assumes less and is the standard method for these questions at A-level.

    For the other 2 questions, yes if you can show it's divisible by say 12, it's obviously divisible by 6.

    And yes you cannot say because it is divisible by 2 it must be divisible by 286 (essentially what you did in your original post), you must show it is divisible by all the factors required.
    What do you mean by all the factors required ? To prove something is divisible by x is it sufficient to show that it is divisible by any two factors of x or must these factors meet certain conditions ?
    • 13 followers
    Offline

    ReputationRep:
    (Original post by member910132)
    But to prove something is divisible by 18 is it sufficient to prove it is divisible by 2 and 6 ?


    What do you mean by all the factors required ? To prove something is divisible by x is it sufficient to show that it is divisible by any two factors of x or must these factors meet certain conditions ?
    Sorry to confuse you, yes what you said is sufficient. In this question its 2 and 3 as you've noticed
    • 0 followers
    Offline

    ReputationRep:
    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.

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?

    this is what you'll be called on TSR

  2. this can't be left blank
    this email is already registered. Forgotten your password?

    never shared and never spammed

  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 completing the slider below you agree to The Student Room's terms & conditions and site rules

  2. Slide the button to the right to create your account

    Slide to join now Processing…

    You don't slide that way? No problem.

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