Results 1 to 12 of 12

Math Help - Divisibility Proofs

  1. #1
    Member
    Joined
    Jul 2011
    Posts
    140

    Divisibility Proofs

    Having a bit of trouble with this one. Can anyone help?

    Many thanks.

    Q. n^3-n is divisible by 3 for n \in \mathbb{N}_o

    Attempt: Step 1: For n = 1...(or P1)
    13 - 1 = 0, which can be divided by 3.

    Step 2: For n = k...
    Assume k3 - k can be divided by 3,
    i.e. k3 - k = 3Z, where Z is an integer...1
    Show that n = k + 1 is true...(i.e. show that P(k + 1) is true),
    i.e. (k + 1)3 - (k + 1) can be divided by 3.
    (k + 1)3 - (k + 1) = (k + 1)(k2 - k + 1) - (k + 1) = ...?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    GJA
    GJA is offline
    Member
    Joined
    Jul 2012
    From
    USA
    Posts
    109
    Thanks
    29

    Re: Divisibility Proofs

    Nice work so far. Try factoring (k+1) out and using your inductive assumption. I think you should be able to get it from there; let me know if this helps. Good luck!
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,150
    Thanks
    591

    Re: Divisibility Proofs

    an alternative:

    n3 - n = n(n2 - 1) = (n - 1)(n)(n + 1).

    these are 3 successive integers, surely one of them is divisible by 3.

    (EDIT)

    your inductive proof is already on the "wrong track".

    (k + 1)3 - (k + 1) = (k + 1)(k + 1)2 - (k + 1)

    = (k + 1)(k2 + 2k + 1) - (k + 1) ← you have expanded (k + 1)2 incorrectly.

    even so this only leads to an expression involving a quadratic in k, and is not very helpful.

    the thing to do is expand (k + 1)3 fully, so we get:

    (k + 1)3 - (k + 1) = k3 + 3k2 + 3k + 1 - k - 1

    = k3 - k + 3(k2 + k)

    = 3z + 3(k2 + k) ← induction hypothesis used HERE

    = 3(z + k2 + k), which is clearly a multiple of 3.
    Last edited by Deveno; August 5th 2012 at 07:48 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: Divisibility Proofs

    Quote Originally Posted by GrigOrig99 View Post
    Step 2: For n = k...
    Assume k3 - k can be divided by 3,
    i.e. k3 - k = 3Z, where Z is an integer...1
    Show that n = k + 1 is true...(i.e. show that P(k + 1) is true)
    n = k + 1 is definitely false because above you let n = k. And the fact that n = k + 1 is not the same as P(k + 1) being true. Also, what is P? It's undefined so far.

    Quote Originally Posted by GrigOrig99 View Post
    (k + 1)3 - (k + 1) = (k + 1)(k2 - k + 1) - (k + 1) = ...?
    (k + 1)3 - (k + 1) ≠ (k + 1)(k2 - k + 1) - (k + 1).

    I recommend fully expanding (k + 1)3 - (k + 1).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jul 2011
    Posts
    140

    Re: Divisibility Proofs

    Ok, continuing on from where I left off:

    k3 - k = 3Z \rightarrow k(k2 - 1) = 3Z \rightarrow k(k + 1)(k - 1) = 3Z \rightarrow (k + 1)(k2 - k) = 3Z...1

    (k + 1)[(k2 - k + 1) - 1]
    (k + 1)[(k2 - k + 1) - 1]
    (k + 1)[k2 - k]
    From 1...(k + 1)[k2 - k] = 3Z

    Is this correct?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jul 2011
    Posts
    140

    Re: Divisibility Proofs

    I'll take a look at the 2 additional posts, as well. I was working on the updated attempt while you guys, Dev. & Emak, were posting your responses .!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: Divisibility Proofs

    Quote Originally Posted by GrigOrig99 View Post
    (k + 1)[(k2 - k + 1) - 1]
    (k + 1)[(k2 - k + 1) - 1]
    (k + 1)[k2 - k]
    From 1...(k + 1)[k2 - k] = 3Z
    What does it have to do with (k + 1)3 - (k + 1) being divisible by 3?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,150
    Thanks
    591

    Re: Divisibility Proofs

    the whole idea of an inductive proof is to show that P(k+1) follows from P(k).

    in this particular instance P(k) is:

    k3 - k = 3*"some integer"

    so P(k+1) is:

    (k+1)3 - (k+1) = 3*"some integer"

    note that we don't require the "some integer" to be the same, or for there even to be some relationship between the 2. they just have to be integers.

    the strategy is to manipulate P(k+1) so that it becomes:

    P(k) and "something else we know is true".

    in this case, that means finding a way to express (k+1)3 - (k+1) in terms of k3 - k and "something else". hopefully, that "something else" will be divisible by 3,

    so that P(k) and "something else that is divisible by 3" together will give us P(k+1).

    so look at the expression (k+1)3 - (k+1). we can obviously get a -k from the -(k+1) part, and the -1 "left over" will go to the "something else". but where are we going to get a k3? from expanding (k+1)3.

    when we expand (k+1)3, we get k3+3k2+3k+1. we take the k3 to go with the -k, so that NOW we have the k3-k we can apply P(k) to. this means that the 32+3k+1 goes to the "something else".

    so now we've "split" (k+1)3 - (k+1) into two parts:

    k3-k (used for our induction hypothesis)
    3k2+3k+1 - 1 (our "something else").

    note that the 1's cancel in our something else, and the rest of it has a 3 in front. so "something else" is divisible by 3. and that's exactly what we need.
    Last edited by Deveno; August 5th 2012 at 08:36 AM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Jul 2011
    Posts
    140

    Re: Divisibility Proofs

    Ok, thanks guys.

    Also, I'm including an image on an example question from the text book I'm using, as I was wondering if the method of answering divisibility proofs there is a bit different from the way you guys do it. n = k appears to be replacing P(k), n = k + 1 replacing P(k + 1) & so on.
    Attached Thumbnails Attached Thumbnails Divisibility Proofs-photo-2-.jpg  
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: Divisibility Proofs

    I think the method is the same. Note that the proof says, "we must show that the statement is true for n = k + 1" and not "we must show n = k + 1 is true." We could denote the fact that the statement in question holds for n by P(n). Deveno did this in post #8. Then the induction step amounts to assuming P(k) for some k and proving P(k + 1).
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    Jul 2011
    Posts
    140

    Re: Divisibility Proofs

    Ok. Thanks for taking a look at that for me.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Super Member
    Joined
    Jun 2012
    From
    AZ
    Posts
    616
    Thanks
    97

    Re: Divisibility Proofs

    Deveno's solution is the simplest. Out of the numbers n-1, n, n+1, exactly one of them will be divisible by 3.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Divisibility Proofs
    Posted in the Pre-Calculus Forum
    Replies: 9
    Last Post: July 18th 2012, 11:51 AM
  2. Divisibility Proofs
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: July 16th 2012, 10:17 AM
  3. Divisibility Proofs
    Posted in the Pre-Calculus Forum
    Replies: 7
    Last Post: July 7th 2012, 09:22 AM
  4. Proofs of rules of divisibility
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 24th 2010, 10:47 AM
  5. Proofs-Divisibility of Integers
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 14th 2009, 11:45 PM

Search Tags


/mathhelpforum @mathhelpforum