Results 1 to 6 of 6

Thread: Math of Induction - Divisbility

  1. #1
    Newbie
    Joined
    Jan 2009
    Posts
    2

    Math of Induction - Divisbility

    I'm trying to prove $\displaystyle 3|(x^3 - x)$ through induction. (and for 5 in $\displaystyle x^5 - x$ but that's for later)
    Done the base case which simplifies to 2
    Assume for $\displaystyle x = k$ evaluates to $\displaystyle k(k + 1) = \mathbb{I}$
    Inductive prove for $\displaystyle x = k + 1$ evaluates to $\displaystyle (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:
    $\displaystyle \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
    21,774
    Thanks
    2823
    Awards
    1
    Assume that $\displaystyle 3|\left( {k^3 - k} \right)$ is true. Then look at:
    $\displaystyle \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 $\displaystyle 3|(x^3 - x)$ through induction. (and for 5 in $\displaystyle x^5 - x$ but that's for later)
    Done the base case which simplifies to 2
    Assume for $\displaystyle x = k$ evaluates to $\displaystyle k(k + 1) = \mathbb{I}$
    I dont understand the stuff you have written....

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

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

    But $\displaystyle (k+1)^3 - (k+1) = (k^3 + 1 + 3k + 3k^2) - (k+1) = (k^3 - k) + 3(k+k^2)$

    By Induction Hypothesis, $\displaystyle 3|k^3 - k$, 3 clearly divides $\displaystyle 3(k^2 + k)$, thus 3 divides the sum $\displaystyle 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
    19,769
    Thanks
    3027
    By the way, you said you were to use induction so that is the way you were answered. But $\displaystyle 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.

    $\displaystyle 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 $\displaystyle 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 $\displaystyle 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; Jan 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
    Thanks
    1

    Divisibility

    Hello everyone -

    It is perhaps interesting to observe that $\displaystyle x^p - x$ is divisible by $\displaystyle p$ for any prime $\displaystyle 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 $\displaystyle (k+1)^p$ are divisible by $\displaystyle p$, when $\displaystyle p$ is prime. This is simply because the numerator of $\displaystyle \frac{p!}{r!(p-r)!}$ has a prime factor $\displaystyle p$ for $\displaystyle 1\le r\le p-1$, but the denominator doesn't.

    Grandad
    Last edited by Grandad; Jan 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: Mar 26th 2010, 02:24 PM
  2. Math Induction Help
    Posted in the Pre-Calculus Forum
    Replies: 12
    Last Post: Dec 6th 2009, 07:19 PM
  3. Math Induction
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: Dec 1st 2008, 09:24 AM
  4. Math Induction...PLEASE HELP!!!!!
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Mar 16th 2008, 01:01 AM
  5. Math Induction
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Feb 29th 2008, 05:40 AM

Search Tags


/mathhelpforum @mathhelpforum