Results 1 to 8 of 8

Math Help - prove by induction 6 divides n^3 -n

  1. #1
    Member
    Joined
    May 2008
    Posts
    94

    Exclamation prove by induction 6 divides n^3 -n

    Hello there!

    I don't get it - what to assume in the following problem for solving by induction

    Prove that 6 divides n^3 - n whenever n is a nonnegative integer

    I tried following:

    assume for "k" --
    k^3 - k = 6r for some integer "r"

    now to prove "k+1" we get:
    (k+1)^3 - (k+1) = k^3 + 3k^2+3k+1 - k - 1
    = (k^3-k) +3k^2+3k
    = 6r + 3k^2+3k by induction
    what should i do after this? I am not getting "6" as a common factor how come 6 divides n^3-n!!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,842
    Thanks
    320
    Awards
    1
    Quote Originally Posted by robocop_911 View Post
    Hello there!

    I don't get it - what to assume in the following problem for solving by induction

    Prove that 6 divides n^3 - n whenever n is a nonnegative integer

    I tried following:

    assume for "k" --
    k^3 - k = 6r for some integer "r"

    now to prove "k+1" we get:
    (k+1)^3 - (k+1) = k^3 + 3k^2+3k+1 - k - 1
    = (k^3-k) +3k^2+3k
    = 6r + 3k^2+3k by induction
    what should i do after this? I am not getting "6" as a common factor how come 6 divides n^3-n!!!
    (k + 1)^3 - (k + 1) = (k + 1)((k + 1)^2 - 1)

    = (k + 1)(k^2 + 2k)

    = k(k + 1)(k + 2)

    What can you say about the factors of this product?

    -Dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2008
    Posts
    94
    Quote Originally Posted by topsquark View Post
    (k + 1)^3 - (k + 1) = (k + 1)((k + 1)^2 - 1)

    = (k + 1)(k^2 + 2k)

    = k(k + 1)(k + 2)

    What can you say about the factors of this product?
    So here we don't have to assume that k^3-k = 6r?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    May 2008
    Posts
    94
    Quote Originally Posted by robocop_911 View Post
    So here we don't have to assume that k^3-k = 6r?
    Ahhh!!! I got it thanks bud!!!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,842
    Thanks
    320
    Awards
    1
    Quote Originally Posted by robocop_911 View Post
    So here we don't have to assume that k^3-k = 6r?
    Huh. I didn't see that. Well you could start by writing k^3 - k = k(k^2 - 1) = (k - 1)k(k + 1) which is automatically divisible by 6 and not worry about it. I guess this problem is just lousy for an induction proof.

    But we should be able to write it as one.

    Assume the argument is true for some n = k. Then we have
    k^3 - k = 6a

    We need to show that (k + 1)^3 - (k + 1) = 6b

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

    = k^3 + 3k^2 + 2k

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

    = 6a + 3k^2 + 3k = 6a + 3k(k + 1)

    See what you can do with that line.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    May 2008
    Posts
    94
    Quote Originally Posted by topsquark View Post
    Huh. I didn't see that. Well you could start by writing k^3 - k = k(k^2 - 1) = (k - 1)k(k + 1) which is automatically divisible by 6 and not worry about it. I guess this problem is just lousy for an induction proof.

    But we should be able to write it as one.

    Assume the argument is true for some n = k. Then we have
    k^3 - k = 6a

    We need to show that (k + 1)^3 - (k + 1) = 6b

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

    = k^3 + 3k^2 + 2k

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

    = 6a + 3k^2 + 3k = 6a + 3k(k + 1)

    See what you can do with that line.

    -Dan

    What should I do with this line??
    = 6a + 3k^2 + 3k = 6a + 3k(k + 1)

    this is the same line why I posted this question!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1
    Quote Originally Posted by topsquark View Post
    (k + 1)^3 - (k + 1) = (k + 1)((k + 1)^2 - 1)

    = (k + 1)(k^2 + 2k)

    = k(k + 1)(k + 2)

    What can you say about the factors of this product?

    -Dan
    EDIT: NVM, you addressed this while I was writing it.

    But is that legitimate? Because we could also say

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

    Now, if we are required to use induction to prove (k-1)k(k+1) is divisible by 6, then why are we not required to use induction when we prove it for k(k+1)(k+2)?

    It seems like circumventing the requirements.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,842
    Thanks
    320
    Awards
    1
    Quote Originally Posted by robocop_911 View Post
    What should I do with this line??
    = 6a + 3k^2 + 3k = 6a + 3k(k + 1)

    this is the same line why I posted this question!
    Don't you think that one of k or k + 1 might be an even number? (That's why I put it into that factored form.)

    -Dan
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove using induction on n that 3 divides (4^n)+5
    Posted in the Number Theory Forum
    Replies: 16
    Last Post: July 2nd 2011, 06:38 AM
  2. Prove 3 divides two integers
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 9th 2010, 09:38 AM
  3. Prove that ab divides c.
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: March 3rd 2010, 09:42 AM
  4. Prove that p divides infinitely many numbers...
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 28th 2010, 04:55 PM
  5. Prove that gcd(a,b) divides lcm[a,b]
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: February 15th 2010, 07:44 PM

Search Tags


/mathhelpforum @mathhelpforum