Thread: Proof by induction.

I have a question:
Prove that $\displaystyle n^{5}-n $ is divisible by 10 for all $\displaystyle 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
$\displaystyle 2,6,12...n(n+1) = \frac{n(n+1)(n+2)}{3}$ etc..

Any help?

Originally Posted by spycrab

I have a question:
Prove that $\displaystyle n^{5}-n $ is divisible by 10 for all $\displaystyle 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
$\displaystyle 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

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

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


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

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

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

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

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

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

$\displaystyle 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, $\displaystyle 5n(n^3 + 1)$ ...

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

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

thank you!

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)

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


P(k+1)

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

If we can show that $\displaystyle (k+1)^5-(k+1)$ must be divisible by 10 if $\displaystyle 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.

I might add that

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

and

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

We can also get to the result without induction.

$\displaystyle 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 $\displaystyle 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 $\displaystyle n + 1 $ is 1 less than a multiple of 5 or $\displaystyle n - 1 $ is 1 more than a multiple of 5.

Taking the first of these possibilities,

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

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