# Homework Help: Stuck on a proof by induction

1. Dec 3, 2009

### grizz45

im stuck on this proof can anyone help?

Is it true that for all natural numbers n, for each natural number x, x^n − x is
divisible by n? If so, prove it; if not, explain why not.

so far i have gotten:

make x=1, ((1)^n) -1 = 0, therefore x=1 is divisible by n

assume true for x=k, ie: (k^n) - k is divisible by n

make x=k+1; ((k+1)^n)-(k+1).......and thats it!!!

2. Dec 3, 2009

### Staff: Mentor

Before attempting to prove it, you should first do some work to see if it's actually true. Test the statement with a number of values of n.

If you believe that it's true, you should be doing your induction on n, not x. Your base case is for n = 1. Can you show that x^1 - x is divisible by 1? If that's too obvious, see if if holds for n = 2. IOW, can you show that x^2 - x is divisible by 2?

x^2 - x = x(x - 1)
If x is even, you're done, since an even number times an odd number is even.
If x is odd, then x - 1 is even, and you're done.

Now, assume that x^n - x is divisible by n, which means that x^n - x = a*n for some integer a.
The final step is to show that x^(n + 1) - x is divisible by (n + 1), using the induction hypothesis that x^n - x is divisible by n.

Last edited: Dec 3, 2009