Results 1 to 6 of 6

Math Help - Mathematical induction

  1. #1
    Newbie
    Joined
    Nov 2008
    Posts
    3

    Mathematical induction

    Hi the problem is:

    Prove that 6 is a factor of n^3+3n^2+2n for all natural numbers n.

    I don't know where to start with these kinds of problems, can anyone help?

    THANKS SO MUCH.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Mathstud28's Avatar
    Joined
    Mar 2008
    From
    Pennsylvania
    Posts
    3,641
    Quote Originally Posted by xoluosox View Post
    Hi the problem is:

    Prove that 6 is a factor of n^3+3n^2+2n for all natural numbers n.

    I don't know where to start with these kinds of problems, can anyone help?

    THANKS SO MUCH.
    Ok so our hypothesis is that n^3+3n^2+2n=n(n+1)(n+2)|6~\forall{n}\in\mathbb{N}

    So lets begin

    Base Step: n=1

    When n=1 we have (1)(1+2)(1+3)=6|6

    So that is true

    Restate the hypothesis: \forall{n}\in\mathbb{N}~n(n+1)(n+2)|6

    Inductive step: Now we have to just using the hypothesis prove that

    (n+1)(n+2)(n+3)|6

    Now rexpanding this we get

    n^3+6n^2+11n+6|6

    Rewriting this we get

    n^3+6n^2+11n+6=n^3+3n^2+2n+3n^2+9n+6=n^3+3n^2+2n+3  (n+1)(n+2)|6

    Now by our hypothesis the first term is divisible by six, so it follows that we must just prove that 3(n+1)(n+2)|6

    Now if n is odd then n+1 is even so n+1|2

    So there is a factor of two in n+1 so there is a factor of six in 3(n+1) and consequently in 3(n+1)(n+2)

    Now if n is even then n+2 is even and the same argument follows.

    So we have proved our iductive step and the result follows.

    EDIT: Moo has informed me that I have the notation backwards, for my sake just pretend that n(n+1)(n+2)|6 means that the left hand side is divides the right hand site.
    Last edited by Mathstud28; November 22nd 2008 at 12:08 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2008
    Posts
    3
    Thank you so much. I didn't know how to set up the equation at all.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    A note on notation.

    When you say n^3 + 2n^2+2n is divisible by 6 (or 6 divides n^3 + 2n^2 + 2n ), we write it like this 6 \mid (n^3 + 2n^2 + 2n).

    _________________________

    Also in the inductive step, you can simply factor out the 3 in that second term and use the fact that if you add two numbers that are divisible by 3, then their sum is also divisible by 3:
    \begin{aligned}(n+1)^3 + 3(n+1)^2 + 2(n+1) & = (n+1)(n+2)(n+3) \\ & = n^3 + 6n^2 + 11n + 6 \\ & = n^2 + 3n^2 + 2n + 3n^2 + 9n + 6 \\ & = \underbrace{(n^2 + 3n^2 + 2n)}_{\text{Inductive Hypothesis}} + \underbrace{3(n^2 + 6n + 3)}_{\text{Clearly divisible by 3}} \end{aligned}
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,824
    Thanks
    713
    Hello, xoluosox!

    The proof depends upon what methods you are allowed.
    . . Direct algebraic proof? .Induction?


    Prove that 6 is a factor of n^3+3n^2+2n for all natural numbers n.
    Here's one approach . . .


    Factor the polynomial: . n(n+1)(n+2)

    We have the product of three consecutive integers.

    Since they must be: . \text{(odd)} \times \text{(even)} \times \text{(odd)}\;\text{ or }\;\text{(even)} \times \text{(odd)} \times \text{(even)}
    . . at least one of the factors is even.
    Hence, the polynomial is divisible by 2.

    It can be shown (you can devise your own proof) that:
    . . the product of three consecutive integers is divisible by 3.

    Got it?

    Follow Math Help Forum on Facebook and Google+

  6. #6
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by xoluosox View Post
    Hi the problem is:

    Prove that 6 is a factor of n^3+3n^2+2n for all natural numbers n.

    I don't know where to start with these kinds of problems, can anyone help?

    THANKS SO MUCH.
    The first two steps should be obvius.

    Now you have to show that (k+1)^3 + 3 (k+1)^2 + 2(k+1) is divisible by 6 under the assumption that k^3 + 3 k^2 + 2k is divisible by 6.

    Note that (k+1)^3 + 3 (k+1)^2 + 2(k+1) = k^3 + 6 k^2 + 11k + 6 = k^3 + 3 k^2 + 2k + (3k^2 + 9k + 6) = \, ....

    where you now need to think about 3k^2 + 9k + 6 \, ....
    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