# Math Help - Proof by induction.

1. ## Proof by induction.

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?

2. 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

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

4. 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.

5. thank you!

6. 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

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

8. 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.