Results 1 to 6 of 6

Thread: 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 $\displaystyle n=k+1$.

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

    Since by inductive hypothesis, 16 divides the expression for $\displaystyle n = k$, all you have to do is verify that 16 divides $\displaystyle (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
    11,152
    Thanks
    731
    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 $\displaystyle 4k^4 + 40k^3 + 180k^2 + 400k + 368$ is already divisible by 4, so all we need to show is that $\displaystyle k^4 + 10k^3 + 45k^2 + 100k + 92$ is divisible by 4.

    So let $\displaystyle k \equiv x$ (mod 4). The polynomial is $\displaystyle x^4 + 2x^3 + x^2$ (mod 4) = $\displaystyle 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 $\displaystyle k^4 + 10k^3 + 45k^2 + 100k + 92$:

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

    Of these terms only the $\displaystyle 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
    11,152
    Thanks
    731
    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 $\displaystyle n=k+1$.

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

    Since by inductive hypothesis, 16 divides the expression for $\displaystyle n = k$, all you have to do is verify that 16 divides $\displaystyle (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
    12,028
    Thanks
    848
    Hello, lisaak!

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

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

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

    Once I came up with that equation, I expanded all the parts
    and ended up with: $\displaystyle 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 $\displaystyle n = k:$

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


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

    . . $\displaystyle 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:

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

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

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

    Therefore, we have proved $\displaystyle 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: Apr 21st 2011, 12:36 AM
  2. Replies: 10
    Last Post: Jun 29th 2010, 12:10 PM
  3. induction help
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: Apr 19th 2010, 05:39 AM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Mar 8th 2009, 09:33 PM
  5. Induction!
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Mar 7th 2008, 04:10 PM

Search Tags


/mathhelpforum @mathhelpforum