# Induction

• Nov 6th 2006, 05:15 PM
lisaak
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.
• Nov 6th 2006, 05:56 PM
Soltras
Hi Lisa.

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.
• Nov 6th 2006, 06:15 PM
topsquark
Quote:

Originally Posted by lisaak
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
• Nov 6th 2006, 06:17 PM
topsquark
Quote:

Originally Posted by Soltras
Hi Lisa.

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
• Nov 6th 2006, 06:33 PM
Soltras
Quote:

Originally Posted by topsquark
(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. :D
• Nov 10th 2006, 08:02 AM
Soroban
Hello, lisaak!

Quote:

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).$