Induction

**lisaak** · November 6th 2006, 05:15 PM

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.

**Soltras** · November 6th 2006, 05:56 PM

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.

**topsquark** · November 6th 2006, 06:15 PM

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

**topsquark** · November 6th 2006, 06:17 PM

Originally Posted by Soltras

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

**Soltras** · November 6th 2006, 06:33 PM

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.

**Soroban** · November 10th 2006, 08:02 AM

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

Thread: Induction

LinkBack

Thread Tools

Display

Induction

Similar Math Help Forum Discussions

Strong induction vs. structural induction?

Rigorously prove the principle of complete induction from mathematical induction??

induction help

Mathemtical Induction Proof (Stuck on induction)

Induction!

Search Tags