Results 1 to 3 of 3

Math Help - Mathematical Induction help

  1. #1
    Junior Member
    Joined
    Mar 2009
    Posts
    30

    Mathematical Induction help

    Use mathematical induction to prove that 6 divides n^3-n, for all natural numbers. (For example, n=0..1..2)


    Im confused on how to set this up.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    Hi

    As you've seen, it's easy to check that 6 divides n^3-n when n=0,1\ \text{or}\ 2.

    Now, to prove that for any k in \mathbb{N}, we have to assume that for some integer n\geq 2\ \ 6 divides n^3-n, and then prove that 6 divides (n+1)^3-(n+1).

    We can write: n^3-n=n(n^2-1)=n(n+1)(n-1).

    Hence (n+1)^3-(n+1)=(n+1)(n+2)n

    An integer is divided by 6 iff it is divided by 2 and 3, and a prime divides a product iff it divides at least a factor.

    If 2 and 3 divide n or (n+1), then they divide (n+1)^3-(n+1).
    If 2 divides n-1, it also divides n+1 and then divides (n+1)^3-(n+1).
    If 3 divides n-1, it also divides n+2 and then divides (n+1)^3-(n+1).

    Therefore 6|(n^3-n)\Rightarrow6|((n+1)^3-(n+1))



    Of course, writing n^3-n=n(n^2-1)=n(n+1)(n-1) gives an immediate but non inductive proof.



    Another proof by induction (maybe more comon, try to do it) consists in, when you assume that 6 divides n^3-n, develop (n+1)^3-(n+1) and you find something which is a sum of n^3-n and an integer x. If you show that x is divided by 6, then 6 divides n^3-n+x=(n+1)^3-(n+1), and you can end your proof.
    Follow Math Help Forum on Facebook and Google+

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

    Induction

    Hello tokio
    Quote Originally Posted by tokio View Post
    Use mathematical induction to prove that 6 divides n^3-n, for all natural numbers. (For example, n=0..1..2)


    Im confused on how to set this up.
    This is the third (and there's a fourth) induction question you've posted in the last couple of days. We're here to help you learn how to succeed at Mathematics, not to do your homework for you.

    I'll start you off:

    P(n) is the propositional function: 6 divides n^3 - n

    Now look at the expression (n+1)^3 - (n+1), and, by removing the brackets, simpifying and re-arranging the terms, see if you can prove that P(n) \Rightarrow P(n+1); in other words, that 6 divides (n+1)^3 - (n+1).

    Show us your working, and, if you can't do it, we'll see about the next stage.

    Grandad

    PS I see someone's beaten me to it. But let's see some working next time.

    PPS Since you have been given a solution, here's an easier one:

    (n+1)^3 - (n+1) = n^3 +3n^2+3n+1 -n-1

    = n^3 +3n^2 +2n

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

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

    Now one of n and (n+1) is always even. So 3n(n+1) is divisible by 6. So P(n) \Rightarrow (n^3 - n) + 3n(n+1) is divisible by 6 \Rightarrow P(n+1).

    P(1) is 1^3 - 1 is divisible by 6, which is true. So P(n) is true \forall n \in \mathbb{N}.

    Last edited by Grandad; March 8th 2009 at 06:18 AM. Reason: Add PPS
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: August 31st 2010, 03:31 PM
  2. Mathematical induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: August 30th 2010, 05:54 AM
  3. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  4. mathematical induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 13th 2009, 05:29 PM
  5. Mathematical Induction
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 18th 2009, 08:35 AM

Search Tags


/mathhelpforum @mathhelpforum