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

[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 n⁵－n is divisible by 30.

I start by proving P(1) is true, that is, 1⁵－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)⁵－(n－1) = 30k
(n－1)*[(n－1)⁵－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!

 

[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=?

 

[eumyang]

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

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.
k⁵ - k = 30x for some x.
Prove true for n = k+1.
(k+1)⁵ - (k+1) = ...?

 

[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 going to 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 :)

 

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

 

[bubokribuck]

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.

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)⁵-(n-1) or just prove P(n) straight away?

 

[Mark44]

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): 1⁵ - 1 is divisible by 30
P(n-1): (n - 1)⁵ - 5 is divisible by 30
P(n): n⁵ - 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 = 30k for some integer k.

 

[bubokribuck]

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

 

[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 n⁵ - n = n(n+1)(n-1)(n²+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.

 

[bubokribuck]

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 n⁵ - n = n(n+1)(n-1)(n²+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.

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 :)

 

[vela]

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

 

[Mark44]

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

From the OP (emphasis added).

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

 

[bubokribuck]

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

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)²+1]
P(n-1) = (n-2)(n-1)(n)[(n-1)²+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)²+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 :)

 

[Mark44]

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)²+1]
P(n-1) = (n-2)(n-1)(n)[(n-1)²+1]

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)⁵ - (n - 1) is divisible by 30."

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

NO! You are assuming that "(n - 1)⁵ - (n -1) is divisible by 30" is a true statement.

, and it will be as if none of the consecutive integers are divisible by 5, the other factor [(n-1)²+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 :)

You're misinterpreting what I said.

You need to assume that P(n - 1) is true; i.e., that (n - 1)⁵ - (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 n⁵ - 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)⁵ - (n -1), which you know by assumption is divisible by 30, to n⁵ - n.

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

 

[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 "n⁵-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, 1⁵-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)⁵-(n-1) = 30k
(n-1)[(n-1)⁴-1] = 30k
(n-1)[(n-1)²-1][(n-1)²+1] = 30k
(n-1)(n-1-1)(n-1+1)[(n-1)²+1] = 30k
(n-1)(n-2)(n)[(n-1)²+1] = 30k

What should I do next?

 

[vela]

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

 

[bubokribuck]

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

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!

 

[vela]

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)⁵ 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*}