Results 1 to 6 of 6

Math Help - Math of Induction - Divisbility

  1. #1
    Newbie
    Joined
    Jan 2009
    Posts
    2

    Math of Induction - Divisbility

    I'm trying to prove 3|(x^3 - x) through induction. (and for 5 in x^5 - x but that's for later)
    Done the base case which simplifies to 2
    Assume for x = k evaluates to k(k + 1) = \mathbb{I}
    Inductive prove for x = k + 1 evaluates to (k + 1)(k + 2)
    But I'm guessing you have to add and minus some value before to incorporate the assumption so I'm guessing we do something here:
    \frac{3k^2 + 9k + 6}{3}
    Don't know what exactly, pointers?

    Sorry about the mundane question. I'm not wired to think the 2 steps ahead for proofs.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,403
    Thanks
    1486
    Awards
    1
    Assume that 3|\left( {k^3  - k} \right) is true. Then look at:
    \left( {k + 1} \right)^3  - \left( {k + 1} \right) = k^3  + 3k^2 + 2k = \left( {k^3  - k} \right) + 3\left( {k^2  + k} \right).
    Is that clearly a multiple of 3?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by sogetthis View Post
    I'm trying to prove 3|(x^3 - x) through induction. (and for 5 in x^5 - x but that's for later)
    Done the base case which simplifies to 2
    Assume for x = k evaluates to k(k + 1) = \mathbb{I}
    I dont understand the stuff you have written....

    But if you substituted x = 2 and checked if 3|2^3 - 2 for the base case, then you are right.(or have taken the easier route 3|1^3 - 1)

    Induction Hypothesis: Assume the result is true for x = k: This means 3|k^3 - k
    We want to prove the Induction Step: 3|(k+1)^3 - (k+1)

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

    By Induction Hypothesis, 3|k^3 - k, 3 clearly divides 3(k^2 + k), thus 3 divides the sum k^3 - k + 3(k^2 + k) = (k+1)^3 - (k+1)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jan 2009
    Posts
    2
    Okay so you add and subtract a k to get the assumed value and a multiple of 3.
    Thanks, got it for 5 | x^5 - x too.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Apr 2005
    Posts
    14,992
    Thanks
    1128
    By the way, you said you were to use induction so that is the way you were answered. But x^3- x= x(x^2- 1)= (x-1)(x)(x+1), the product of three consecutive integers (assuming x is an integer). One of them has to be a multiple of 3.

    x^5- x= x(x^4-1)= x(x^2-1)(x^2+ 1)= x(x-1)(x+1)(x^2+1) is a little harder. If x is a multiple of 5, then we are done. if x= 5n+1, then x-1= 5n, a multiple of 5, and we are done. If x= 5n+ 2, then neither x-1= 5n+1 nor x+1= 5n+ 3 is a multiple of 5 but x^2+ 1= 25n^2+ 20n+ 4+ 1= 5(5n^2+ 4n+ 1) is a multiple of 5. If x= 5n+ 3, then neither x-1= 5n+2 nor x+1= 5n+4 is a multiple of 5 but x^2+ 1= 25n^2+ 30n+ 9+ 1= 5(5n^2+ 6n+ 2) is a multiple of 5. Finally, if x= 5n+4, then x+1= 5n+ 5= 5(n+1) is a multiple of 5.
    Last edited by HallsofIvy; January 2nd 2009 at 01:04 PM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570

    Divisibility

    Hello everyone -

    It is perhaps interesting to observe that x^p - x is divisible by p for any prime p.

    The proof (by induction) follows exactly the same lines as before, noting that, with the exception of the first and last terms, all the coefficients in the expansion of (k+1)^p are divisible by p, when p is prime. This is simply because the numerator of \frac{p!}{r!(p-r)!} has a prime factor p for 1\le r\le p-1, but the denominator doesn't.

    Grandad
    Last edited by Grandad; January 3rd 2009 at 12:25 AM. Reason: Addition of the condition on r
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Math Induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 26th 2010, 02:24 PM
  2. Math Induction Help
    Posted in the Pre-Calculus Forum
    Replies: 12
    Last Post: December 6th 2009, 07:19 PM
  3. Math Induction
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: December 1st 2008, 09:24 AM
  4. Math Induction...PLEASE HELP!!!!!
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 16th 2008, 01:01 AM
  5. Math Induction
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: February 29th 2008, 05:40 AM

Search Tags


/mathhelpforum @mathhelpforum