1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Stuck on a proof by induction

  1. Dec 3, 2009 #1
    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. jcsd
  3. Dec 3, 2009 #2

    Mark44

    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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Stuck on a proof by induction
  1. Induction Proof (Replies: 7)

  2. Induction proof (Replies: 1)

  3. Proof By Induction (Replies: 2)

  4. Proof by induction (Replies: 1)

  5. Proof by Induction (Replies: 3)

Loading...