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!

Prove (n^5 - n) is divisible by 5 by induction

  1. Jul 20, 2008 #1
    here's what Ive done so far...

    P(n) = n^5 - n
    n(n-1)(n^3+n+1)
    when n = 5
    5 * 4* 131 = 620
    620 is a factor of 5. therefore true for n=5

    assume true n=k
    P(k) = k^5 - k

    when n = k+1

    P(k+1) = (k+1)(k+1-1)((k+1)^3 + k+2)
    = (k+1)(k)(k^3 + 3k^2 + 3k + 1 + k + 2)
    = (k+1)(k)(k^3 + 3k^2 + 4k + 3)
    = (k^2+k)(k^3 + 3k^2 + 4k + 3)
    = k^5 + 4k^4 + 7k^3 + 7k^2 + 3k

    what shall I do from there?

    thanks xxx
     
  2. jcsd
  3. Jul 20, 2008 #2

    mathman

    User Avatar
    Science Advisor
    Gold Member

    (n+1)^5=n^5+5n^4+10n^3+10n^2+5n+1
    Therefore (n+1)^5-(n+1)=n^5-n+K, where K is divisible by 5.
     
  4. Jul 21, 2008 #3

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Fizza, why do you start with n= 5 as base case? The statement is also true for n= 1, 2, 3, and 4.

    Also you did not use the fact that you are assuming k5- k is a multiple of 5. Follow mathman's suggestion.
     
  5. Jul 21, 2008 #4
    I'm trying to figure out how the problem was built in the first place.

    I'd imagine a similar statement is true for any prime power, since the 'prime rows' of the Pascal triangle are divisible by that prime (except for the ending 1's).
     
  6. Jul 21, 2008 #5

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    So you are asking, "Is it true that np- n is divisible by p for p any prime?"

    Yes, it is and for exactly the reason you state: if p is prime then [itex]\left(\begin{array}{c}p \\ i\end{array}\right)[/itex] for p prime and 0< i< p is divisible by p. That itself can be proven directly from the definition:
    [tex]\left(\begin{array}{c}p \\ i\end{array}\right)= \frac{p!}{i!(p-i)!}[/tex]
    as long as i is neither 0 nor p, 0<p-i< p and so neither i! nor (p- i)! have a factor of p. Since p! does, the binomial coefficient is divisible by p. (We need p to be prime so that other factors in i! and (p- i)! do not "combine" to cancel p.)

    Now, to show that np- n is divisible by p, do exactly what mathman suggested.

    First, when n= 1, 1p- 1= 0 which is divisible by p. Now assume the statement is true for some k: kp- k= mp for some integer m. Then, by the binomial theorem,
    [tex](k+1)^p= \sum_{i=0}^p \left(\begin{array}{c}p \\ i\end{array}\right) k^i[/itex]
    subtracting k+1 from that does two things: first it cancels the i=0 term which is 1. Also we can combine the "k" with the i= p term which is kp so we have kp- k= mp. The other terms, all with 0< i< p, contain, as above, factors of p.
     
    Last edited: Jul 21, 2008
  7. Aug 16, 2008 #6
    Hello hall of Ivy

    What would be the converse of this ^^^? Could you use "the assuming the opposite" method to prove whether or not this holds?

    cheers
     
  8. Aug 16, 2008 #7

    LowlyPion

    User Avatar
    Homework Helper

    Not to be too picky but your example shows n = 5 yields 620. It should be 2620, but of course satisfies the condition.

    Secondly and more importantly I don't think the factors of n^5 - n are simplified enough.

    I would note that:
    n^5 - n = n(n^4-1) = n*(n^2-1)*(n^2+1) = (n-1)*n*(n+1)*(n^2+1)

    Perhaps you can exploit the fact that for any n you necessarily have the number above and below that number that must be a factor of the result?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Prove (n^5 - n) is divisible by 5 by induction
  1. Prove Divisibility (Replies: 2)

  2. Tables in -5 (Replies: 5)

  3. 5 and 7 (Replies: 6)

Loading...