# How to prove that n^5－n is divisible by 30

1. Oct 27, 2011

### bubokribuck

Hi there all, I have a question that I sincerely don't know how to solve and so would like to discuss it with you guys for any possible solutions.

Here's the problem:

I need to prove by induction that n5－n is divisible by 30.

I start by proving P(1) is true, that is, 15－1=0=30k where k=0. This shows that P(1) is divisible by 30 so it's true.

Next, I assume that P(n－1) is true and use this assumption to prove that P(n) is true.

I wrote:

P(n－1) => (n－1)5－(n－1) = 30k
(n－1)*[(n－1)5－1] = 30k

Then I had no idea what to do next. I know at the end I have to prove that P(n－1) is a multiple of 30, but how should I prove that by induction? Can anyone help me with this please!!

Last edited: Oct 27, 2011
2. Oct 27, 2011

### Matterwave

Isn't proof by induction, you assume the n-1 case is true, and then with that assumption, if you show that it's also true for n, then you have proved the statement?

So, you proved that n=1 is true. Now, assume then that (n-1)^5-(n-1)=30k is true, for k an integer, then what is n^5-n=?

3. Oct 27, 2011

### eumyang

You mean k = 0.

When I was taught induction we didn't reuse the variable n. So in your problem, the induction proof would start like this:

Base case: n = 1 (which you did)

Inductive case: assume true for n = k.
k5 - k = 30x for some x.
Prove true for n = k+1.
(k+1)5 - (k+1) = ...?

4. Oct 27, 2011

### bubokribuck

Oops, pardon me for the poor wording, I have rewritten the sentence and corrected the k=0 bit, hopefully it's making more sense now ^^"

@Matterwave
Well, if (n-1)^5-(n-1)=30k is true, for k an integer, then what is n^5-n=30j, for j another integer other than k, is that right? But how is this gonna prove that P(n-1) is divisible by 30?

@eumyang
Our teacher taught us quite differently, she told us that to prove by induction, we
1. prove that P(1) is true;
2. assume P(n-1) is true and use this assumption to prove that P(n) is true.
so we need to substitute (n-1) into n when doing the second step, and prove that P(n) is true; n is the letter that we normally use in all cases, but thanks for telling me the correct way to denote :)

5. Oct 27, 2011

### Matterwave

Mine and eumyang's methods are the same, except you redefine n->n-1. (I take the n-1 to be assumed and then prove the n case, while he takes n to be assumed and then prove the n+1 case).

You don't need to prove that P(n-1) is divisible by 30. You ASSUME it is, and then just prove p(n) is divisible by 30.

6. Oct 27, 2011

### bubokribuck

I know that in order for p(n) to be divisible by 30, it must also be divisible by 2,3,5. So does it mean that as long as I can prove that the consecutive integers of P(n) are divisible by 2,3,5, I have proved P(n) is true? But this doesn't relate anything to the n-1 case though, is there something missing? Do I still have to write it out like (n-1)5-(n-1) or just prove P(n) straight away?

7. Oct 27, 2011

### Staff: Mentor

If you don't use P(n-1), then you haven't done an induction proof.

It's not clear to me that you understand what P(n) represents. What you have is a sequence of statements.

P(1): 15 - 1 is divisible by 30
P(n-1): (n - 1)5 - 5 is divisible by 30
P(n): n5 - 5 is divisible by 30

You are assuming that P(n-1) is true and show that as long as P(n - 1) is true, then P(n) will necessarily be true. You need to work in the fact that (n - 1)5 - 5 = 30k for some integer k.

8. Oct 28, 2011

### bubokribuck

I have solved the problem. Thanks for everyone's help! :)

Last edited: Oct 28, 2011
9. Oct 28, 2011

### dextercioby

The problem can be solved more easily without induction. Take advantage that 30 = 2*3*5 and that 2,3,5 are coprimes (actually primes). Then n5 - n = n(n+1)(n-1)(n2+1). The product of the first 3 factors is divisible by 2*3, while the last factor is divisible by 5 for n=5k-2 and n=5k-3, as one can easily show.

10. Oct 28, 2011

### bubokribuck

This is what I did except that I substituted n for n-1. So this idea will work for either n or n-1, or even n+1 as well :)

11. Oct 28, 2011

### vela

Staff Emeritus
Was the problem to prove it by induction or simply just to prove it?

12. Oct 28, 2011

### Staff: Mentor

13. Oct 28, 2011

### bubokribuck

It's to be proved by induction.

dextercioby indicated that n(n+1)(n-1)(n2+1), I substituted n for n-1 so that
P(n-1) = (n-1)(n-1+1)(n-1-1)[(n-1)2+1]
P(n-1) = (n-2)(n-1)(n)[(n-1)2+1]

Either way, there would be three consecutive integers, so the theory that "at least one of them is even and at least one of them is divisible by 3" will apply anyway, so P(n-1) is divisible by 6. Next I just need to prove P(n-1) is also divisible by 5, and it will be as if none of the consecutive integers are divisible by 5, the other factor [(n-1)2+1] will be divisible by 5. So in conclusion, P(n-1) is divisible by 2,3,5, so it must be divisible by 30 too. At this stage, I have proved P(n-1) is true, and as long as P(n-1) is true P(n) will necessarily be true. This is what Mark44 told me :)

14. Oct 28, 2011

### Staff: Mentor

First off, P(n-1) is not a number that is equal to something. As I said before, it represents one statement. In this case, it represents the statement, "(n - 1)5 - (n - 1) is divisible by 30."
NO! You are assuming that "(n - 1)5 - (n -1) is divisible by 30" is a true statement.
You're misinterpreting what I said.

You need to assume that P(n - 1) is true; i.e., that (n - 1)5 - (n -1) is divisible by 30. This is the induction hypothesis.

Then use this assumption to show (prove) that P(n) is true; i.e., that n5 - n is divisible by 30 is also a true statement. This is the induction step.

The key here is to be able to go from (n - 1)5 - (n -1), which you know by assumption is divisible by 30, to n5 - n.

So the equation to start working on is (n - 1)5 - (n -1) = 30k (for some integer k).

Last edited: Oct 28, 2011
15. Oct 28, 2011

### bubokribuck

@Mark44

Thanks for telling me that P(n) is a statement, I thought it was a function like f(x), but obviously it's not. It looks like I've used a completely different method to prove other than by induction :(

Let me write it out all again:

P(n) represents the statement that "n5-n is divisible by 30".

In order to prove this statement is true, we first need to prove P(1) is true =>
when n=1, 15-1=0=30k where k=0
We have proved that P(1) is true.

Next, we assume that P(n-1) is true, and we use this assumption to prove that P(n) is true.

P(n-1) =>

(n-1)5-(n-1) = 30k
(n-1)[(n-1)4-1] = 30k
(n-1)[(n-1)2-1][(n-1)2+1] = 30k
(n-1)(n-1-1)(n-1+1)[(n-1)2+1] = 30k
(n-1)(n-2)(n)[(n-1)2+1] = 30k

What should I do next?

Last edited: Oct 28, 2011
16. Oct 28, 2011

### vela

Staff Emeritus
Try using $n^5-n = [(n-1)+1]^5-[(n-1)+1]$. Expand in terms of (n-1), and then use the induction hypothesis to replace (n-1)5-(n-1) with 30k. Then all you have to do is show the remaining terms are divisible by 30.

The divisibility by 5 and 2 will be easy to show. You may have to think a bit about showing it's divisible by 3.

17. Oct 29, 2011

### bubokribuck

Hi,I'm struggled to expand $[(n-1)+1]^5-[(n-1)+1]$ in terms of (n-1). Had a few tries all failed. Can you show me how to do it please. Thanks!

18. Oct 29, 2011

### vela

Staff Emeritus
You use the binomial theorem
$$(a+b)^n = \binom{n}{0}a^n b^0 + \cdots + \binom{n}{k}a^{n-k}b^k + \cdots + \binom{n}{n}a^0 b^n.$$or simply multiply out (x+1)5 and then set x=n-1 at the end. Either way, you end up with
\begin{align*}
(x+1)^5 &= x^5 + 5x^4+10x^3+10x^2+5x+1 \\
&= (n-1)^5 + 5(n-1)^4+10(n-1)^3+10(n-1)^2+5(n-1)+1
\end{align*}