Results 1 to 5 of 5

Math Help - [SOLVED] should be really simple... prove that n^3+14n is divisible by 3

  1. #1
    Junior Member
    Joined
    Sep 2007
    Posts
    30

    [SOLVED] should be really simple... prove that n^3+14n is divisible by 3

    I'm probably just being dumb now, but I cannot seem to prove that n^3+14n is divisible by 3. I am trying induction:

    Base case: n=1. Then 1+15=15, which is divisible by 3.

    Inductive step:
    (n+1)^3+14(n+1)
    = n^3+3n^2+17n+15
    = (n+1)^2(n^2+2n+15)

    But then from here, I'm stuck. Any suggestions?

    EDIT: this is for all ints >= 0.

    Thanks in advance!
    Last edited by horan; February 17th 2009 at 06:19 PM. Reason: this is for all ints >= 0.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Reckoner's Avatar
    Joined
    May 2008
    From
    Baltimore, MD (USA)
    Posts
    1,024
    Thanks
    75
    Awards
    1

    Smile

    Quote Originally Posted by horan View Post
    Inductive step:
    (n+1)^3+14(n+1)
    = n^3+3n^2+17n+15
    = (n+1)^2(n^2+2n+15)
    In problems like these, avoid your habit from algebra of always factoring everything completely:

    n^3+3n^2+17n+15

    =n(n^2+3n+17)+15

    By inductive hypothesis, 3\mid n\Rightarrow n=3p,\;\exists p\in\mathbb{Z} so we have

    n(n^2+3n+17)+15 = 3p(n^2+3n+17)+3\cdot5 = 3(pn^2+3pn+17p+5)

    =3q,\;q=pn^2+3pn+17p+5\in\mathbb{Z}\text.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,660
    Thanks
    600
    Hello, horan!

    I'll slightly modify your work . . .


    Prove that: . n^3+14n is divisible by 3.

    Verify S(1)\!:\;\;1^3 + 14(1) \:=\:15 ... divisible by 3.


    Assume S(k)\!:\;\;k^3 + 14k \:=\:3a\;\text{ for some integer }a


    Inductive step: S(k+1)

    . . (n+1)^3+14(n+1) \;=\;n^3+3n^2+17n+15

    . . = \;n^3 + 3n^2 + (14n + 3n) + 15 \;=\;(n^3 + 14n) + (3n^2 + 3n + 15)

    . . = \;\underbrace{n^3 + 14n}_{\text{This is }3a} + \underbrace{3(n^2 + n + 5)}_{\text{a multiple of 3}}


    Therefore, S(k+1) is divisible by 3.
    . . The inductive proof is complete.

    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member JaneBennet's Avatar
    Joined
    Dec 2007
    Posts
    293
    Hello, horan!

    Note that 14\equiv-1\pmod3.

    Hence n^3+14n=n(n^2+14)\equiv n(n^2-1)\pmod3

    and n(n^2-1)=(n-1)n(n+1) is divisible by 3 because it’s the product of 3 consecutive integers.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Sep 2007
    Posts
    30
    ah, that helps a lot. thanks!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove 16^m + 10m -1 is always divisible by 25
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: March 9th 2011, 09:15 AM
  2. Replies: 1
    Last Post: May 7th 2010, 11:49 PM
  3. Prove n is divisible by 2^m
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 24th 2008, 03:54 AM
  4. prove that then n is divisible by 11
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 23rd 2008, 11:05 PM
  5. Prove n is divisible by 3
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 23rd 2008, 06:10 PM

Search Tags


/mathhelpforum @mathhelpforum