# Induction proof

1. Jul 14, 2011

### Punkyc7

Find the largest natural number m such that n^3 -n is divisible by m for n element N. Prove your assertion.

How exactly do you begin this

im thinking the largest m could possible be is n^3 -n, but im not sure.

To be divisible we know that

mk=n^3-n for some k

Last edited: Jul 14, 2011
2. Jul 15, 2011

### Dick

Well, sure n^3-n divides n^3-n. But I doubt that's what they mean. I think they mean a proper divisor, i.e. m<n^3-n. What number LESS than n^3-n divides n^3-n and can you show it's the largest possible?

3. Jul 15, 2011

### HallsofIvy

Staff Emeritus
How can you factor $n^3- n$?

4. Jul 15, 2011

### Punkyc7

n(n^2-1) is that this question was asking for?

And from there you induction on n^3-n and show that n^2 -1 is the largest number

5. Jul 15, 2011

### micromass

Staff Emeritus
Take n=3, what is the largest proper divisor of n3-n then?

6. Jul 15, 2011

### Punkyc7

would it be 12...which is not n^2-1

7. Jul 15, 2011

### micromass

Staff Emeritus
But which is the half of n3-n. Can you show that the half is always the largest divisor??

8. Jul 15, 2011

### Punkyc7

I going to guess you can. So we assume that (n^3-n)/2 is the largest and we want to show

(n+1^3-n+1)/2 is the largest divisor of n+1^3-n+1

9. Jul 15, 2011

### micromass

Staff Emeritus
Isn't it obvious that $\frac{n^3-n}{2}$ is the largest divisor?? The only thing you need to show is that 2 divides n3-n. That's what you need to show by induction.

10. Jul 15, 2011

### Punkyc7

so we show that 2 divides when n is odd and when n is even.

Then we show 2 divides n+1^3-n+1?

11. Jul 15, 2011

### micromass

Staff Emeritus
Indeed, you must show that $(n+1)^3-(n+1)$ is even when $n^3-n$ is.

12. Jul 15, 2011

### Punkyc7

and do the same thing when its odd.

Now do I have to show that (n+1^3−n+1)/2 is the largest divisor of n+1^3-n+1, or do I just have to show two divides it.

13. Jul 15, 2011

### tiny-tim

Hi Punkyc7!
Doesn't it mean find the highest common factor of every value of n3 - n ?

14. Jul 15, 2011

### Punkyc7

Hi tiny tim,

it should say for all n element N, im going to edit that.

I cant edit it the edit button is gone so it should say

Find the largest natural number m such that n^3 -n is divisible by m for all n element N. Prove your assertion

15. Jul 15, 2011

### hunt_mat

$n^{3}-n=n(n^{2}-1)=(n-1)n(n+1)$

16. Jul 15, 2011

### Punkyc7

ok, so how is knowing the roots helpful?

17. Jul 16, 2011

### Char. Limit

Say that we have the product n*(n+1). If n is divisible by two, is the product? If n is NOT divisible by two, is the product? (AKA is n*(n+1)/2 an integer for all even natural numbers n? How about all odd natural numbers n?)

18. Jul 16, 2011

### Punkyc7

im going to say yes to the first part

yes for the second part because even numbers can be divided by 2

so it would be an integer for all even natural number

wouldnt it also be true for odd

19. Jul 16, 2011

### Char. Limit

Indeed. So if n(n+1)/2 is an integer for all natural numbers n, isn't (n-1)(n+1)n/2 also an integer for all natural numbers n?

20. Jul 16, 2011

### Punkyc7

I want to say yes