Results 1 to 6 of 6

Math Help - Induction

  1. #1
    Newbie
    Joined
    Nov 2006
    Posts
    7

    Induction

    Alright, here is the problem:
    using the principle of mathematical induction prove that, for any positive integer n,
    n^4 + (n+1)^4 + (n+2)^4 + (n+3)^4 + 14 is divisible by 16.

    What I have done so far is the base step, and I have assumed the statement is true for n=k.
    For n=k+1 I have added (k+4)^4 - k^4 to the expression for n=k. Once I came up with that equation, I expanded all the parts...
    I ended up with 4k^4 + 40k^3 + 180k^2 + 400k + 368
    now I have no idea where to go with it...

    thank-you in advance for any help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Jun 2006
    From
    San Diego
    Posts
    101
    Hi Lisa.
    Use your inductive assumption.

    You want to see if the statement is true for n=k+1.

    Well you seem to have correctly observed that the expression for n = k+1 is just the expression for n = k with (k+4)^4-k^4 added on.

    Since by inductive hypothesis, 16 divides the expression for n = k, all you have to do is verify that 16 divides (k+4)^4-k^4.

    Expand this and you will see every term is divisible by 16. (you may find it easy to expand if you take advantage of its form as a difference of squares).

    In your proof, you might want to explain that if a number (16) divides two numbers, then it divides their sum as well. Presumably, this property has been discussed/proved in your class or textbook by now, so just mentioning the fact will probably suffice.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,815
    Thanks
    316
    Awards
    1
    Quote Originally Posted by lisaak View Post
    Alright, here is the problem:
    using the principle of mathematical induction prove that, for any positive integer n,
    n^4 + (n+1)^4 + (n+2)^4 + (n+3)^4 + 14 is divisible by 16.

    What I have done so far is the base step, and I have assumed the statement is true for n=k.
    For n=k+1 I have added (k+4)^4 - k^4 to the expression for n=k. Once I came up with that equation, I expanded all the parts...
    I ended up with 4k^4 + 40k^3 + 180k^2 + 400k + 368
    now I have no idea where to go with it...

    thank-you in advance for any help.
    Do you know "modular" Mathematics?

    Note that 4k^4 + 40k^3 + 180k^2 + 400k + 368 is already divisible by 4, so all we need to show is that k^4 + 10k^3 + 45k^2 + 100k + 92 is divisible by 4.

    So let k \equiv x (mod 4). The polynomial is x^4 + 2x^3 + x^2 (mod 4) = x^2(x^2 + 2x + 1) = x^2(x+1)^2 (mod 4)

    So no matter what value of x we have, the polynomial is divisible by an even number squared. (Either x or x+1.) Thus the polynomial is divisible by 4 and thus the original polynomial is divisible by 16.
    -------------------------------------------------------------------------

    If you can't follow the above argument, note that k takes the form of one of the following possibilities:
    k = 4m (x = 0)
    k = 4m + 1 (x = 1)
    k = 4m + 2 (x = 2)
    k = 4m + 3 (x = 3)
    where m is some integer.

    Now put k = 4m + x in k^4 + 10k^3 + 45k^2 + 100k + 92:

    x^4 + (16m + 10)x^3 + (96m^2+120m+45)x^2 + (256m^3+480m^2+360m+100)x + (256m^4+640m^3+720m^2+400m+92)

    Of these terms only the x^4 + 10x^3 + 45x^2 is not immediately divisible by 4 (due to the coefficients being divisible by 4). So if we can show this is divisible by 4 for all x = 0, 1, 2, 3 then the whole polynomial does as well. You can simply plug each of these values in to verify that it does.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,815
    Thanks
    316
    Awards
    1
    Quote Originally Posted by Soltras View Post
    Hi Lisa.
    Use your inductive assumption.

    You want to see if the statement is true for n=k+1.

    Well you seem to have correctly observed that the expression for n = k+1 is just the expression for n = k with (k+4)^4-k^4 added on.

    Since by inductive hypothesis, 16 divides the expression for n = k, all you have to do is verify that 16 divides (k+4)^4-k^4.

    Expand this and you will see every term is divisible by 16. (you may find it easy to expand if you take advantage of its form as a difference of squares).

    In your proof, you might want to explain that if a number (16) divides two numbers, then it divides their sum as well. Presumably, this property has been discussed/proved in your class or textbook by now, so just mentioning the fact will probably suffice.
    (Chuckles) Well, that was a lot easier than mine!

    -Dan
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jun 2006
    From
    San Diego
    Posts
    101
    Quote Originally Posted by topsquark View Post
    (Chuckles) Well, that was a lot easier than mine!

    -Dan
    Yours is much better actual analysis of what's really going on though, and it is also providing me with a great modular arithmetic brain refresh which I badly need.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,657
    Thanks
    598
    Hello, lisaak!

    Prove by mathematical induction that:
    n^4 + (n+1)^4 + (n+2)^4 + (n+3)^4 + 14 is divisible by 16 for any positive integer n.

    What I have done so far is the base step: S(1)
    and I have assumed the statement is true for n=k:\;S(k)

    For n=k+1, I have added (k+4)^4 - k^4 to the expression for n=k.

    Once I came up with that equation, I expanded all the parts
    and ended up with: 4k^4 + 40k^3 + 180k^2 + 400k + 368
    now I have no idea where to go with it.

    Your game plan is excellent . . . you're that close to the punch line.


    We assume the statement is true for n = k:

    . . k^4 + (k+1)^4 + (k+2)^4 +(k+3)^4 + 14 \;=\;16a for some integer a.


    Add (k+4)^4 - k^4 to both sides:

    . . k^4 + (k+1)^4 + (k+2)^4 + (k+3)^4 + (k+4)^4 + 14 + (k+4)^4 - k^4\;=\;16a + (k+4)^4 - k^4


    We have:

    . . (k+1)^4 + (k+2)^4 + (k+3)^4 + (k+4)^4 + 16 \;= \;16a + k^4 + 16k^3 + 96k^2 + 256k + 256 - k^4

    . . (k+1)^4 + (k+2)^4 + (k+3)^4 + (k+4)^4 + 16 \;= \;16a + 16k^3 + 96k^2 + 256k + 256

    . . \underbrace{(k+1)^4 + (k+2)^4 + (k+3)^4 + (k+4)^4 + 16}_{\text{This is S(k+1)}} \;= \;\underbrace{16(a + k^3 + 6k^2 + 16k + 16)}_{\text{This is divisible by 16}}

    Therefore, we have proved S(k+1).

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 12:36 AM
  2. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  3. induction help
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: April 19th 2010, 05:39 AM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  5. Induction!
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 7th 2008, 04:10 PM

Search Tags


/mathhelpforum @mathhelpforum