Proof by induction.

**spycrab** · August 22nd 2010, 01:03 PM

I have a question:
Prove that $n^{5}-n$ is divisible by 10 for all $n\ge2$ .

Since my current chapter is on induction, I figure it has something to do with induction, I don't really know. But all the induction I've learned in this chapter looks something like
$2,6,12...n(n+1) = \frac{n(n+1)(n+2)}{3}$ etc..

Any help?

**skeeter** · August 22nd 2010, 01:11 PM

Originally Posted by spycrab

I have a question:
Prove that $n^{5}-n$ is divisible by 10 for all $n\ge2$ .

Since my current chapter is on induction, I figure it has something to do with induction, I don't really know. But all the induction I've learned in this chapter looks something like
$2,6,12...n(n+1) = \frac{n(n+1)(n+2)}{3}$ etc..

Any help?

follow the procedure for proof by induction.

1. show the statement is true for n = 2

2. assuming the statement is true for n, show that the statement is true for n+1

**spycrab** · August 22nd 2010, 01:23 PM

Yes, I know that, but what I'm trying to say is how do you show that it is divisible by 10

**skeeter** · August 22nd 2010, 01:50 PM

someone may offer a shorter solution, but here's the way I did it ...

$2^5 - 2 = 30 = 3 \cdot 10$ ... true for $n = 2$

$(n+1)^5 - (n+1) =$

$n^5 + 5n^4 + 10n^3 + 10n^2 + 5n + 1 - n - 1 =$

$n^5 - n + 5n^4 + 10n^3 + 10n^2 + 5n =$

$(n^5 - n) + 10(n^3 + n^2) + 5n(n^3 + 1)$

since the statement is true for $n$ , then $n^5 - n$ can be written in the form $10k$ , where $k$ is an integral value ...

$10k + 10(n^3 + n^2) + 5n(n^3 + 1)$

the first term is a multiple of 10, as is the second term.

for the 3rd term, $5n(n^3 + 1)$ ...

if $n$ is even, then $5n$ is a multiple of 10.

if $n$ is odd, then $n^3 + 1$ is even, making the 3rd term also a multiple of 10.

**spycrab** · August 22nd 2010, 01:52 PM

thank you!

**Archie Meade** · August 22nd 2010, 02:15 PM

Yes, skeeter's method is exactly how I did it also.
I would word it slightly differently, but that is just my way!

P(k)

$k^5-k$ is divisible by 10 ?

P(k+1)

$k^5-k$ being divisible by 10 causes $(k+1)^5-(k+1)$ to also be divisible by 10 ?

If we can show that $(k+1)^5-(k+1)$ must be divisible by 10 if $k^5-k$ is,

then we've shown that if P(k) is true for k=2, this causes P(k) to be true for k=3,
which causes P(k) to be true for k=4....
a never-ending chain of cause and effect.

Then P(k) being true for k=2, causes P(k) to be true for all k above 2
in the natural number system.

We never know that the original statement is true until after we have
validated P(k+1) and checked the formula for k=2.

K and k+1 are used instead in the notation instead of n and n+1 merely to focus in on
all pairs of adjacent terms.

**Jester** · August 22nd 2010, 02:20 PM

I might add that

$(n+1)^5-(n+1) = n^5 - n + 5n(n+1)(n^2+n+1)$

and

$10| n^5-n$ and $10|5n(n+1)$ .

**BobP** · August 23rd 2010, 02:43 AM

We can also get to the result without induction.

$N = n^5-n=n(n^4-1)=n(n^2-1)(n^2+1)=n(n-1)(n+1)(n^2+1)$

The RHS contains the product of three consecutive integers, so one of them must be even, so $N$ is divisible by 2.

If one of these three is divisible by 5 also then we are done, so assume that this isn't the case, in which case either $n + 1$ is 1 less than a multiple of 5 or $n - 1$ is 1 more than a multiple of 5.

Taking the first of these possibilities,

let $n+1 = 5p-1,$ say, then $n=5p-2,$

so $n^2+1=(5p-2)^2+1=25p^2-20p+5$ which is divisible by 5, and in which case so is $N$ and so $N$ is divisible by 10. Similarly for the other possibility.

Math Help - Proof by induction.

LinkBack

Thread Tools

Display

Proof by induction.

Similar Math Help Forum Discussions

Proof by Induction

Proof by induction

Mathemtical Induction Proof (Stuck on induction)

Proof by Induction??

Proof with algebra, and proof by induction (problems)

Search Tags