1. Limited time only! Sign up for a free 30min personal 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!

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

  1. Oct 27, 2011 #1
    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 n5-n is divisible by 30.

    I start by proving P(1) is true, that is, 15-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)5-(n-1) = 30k
    (n-1)*[(n-1)5-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!!
     
    Last edited: Oct 27, 2011
  2. jcsd
  3. Oct 27, 2011 #2

    Matterwave

    User Avatar
    Science Advisor
    Gold Member

    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=?
     
  4. Oct 27, 2011 #3

    eumyang

    User Avatar
    Homework Helper

    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.
    k5 - k = 30x for some x.
    Prove true for n = k+1.
    (k+1)5 - (k+1) = ...?
     
  5. Oct 27, 2011 #4
    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 gonna 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 :)
     
  6. Oct 27, 2011 #5

    Matterwave

    User Avatar
    Science Advisor
    Gold Member

    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.
     
  7. Oct 27, 2011 #6
    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)5-(n-1) or just prove P(n) straight away?
     
  8. Oct 27, 2011 #7

    Mark44

    Staff: Mentor

    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): 15 - 1 is divisible by 30
    P(n-1): (n - 1)5 - 5 is divisible by 30
    P(n): n5 - 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 - 5 = 30k for some integer k.
     
  9. Oct 28, 2011 #8
    I have solved the problem. Thanks for everyone's help! :)
     
    Last edited: Oct 28, 2011
  10. Oct 28, 2011 #9

    dextercioby

    User Avatar
    Science Advisor
    Homework Helper

    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 n5 - n = n(n+1)(n-1)(n2+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.
     
  11. Oct 28, 2011 #10
    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 :)
     
  12. Oct 28, 2011 #11

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    Was the problem to prove it by induction or simply just to prove it?
     
  13. Oct 28, 2011 #12

    Mark44

    Staff: Mentor

    From the OP (emphasis added).
     
  14. Oct 28, 2011 #13
    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)2+1]
    P(n-1) = (n-2)(n-1)(n)[(n-1)2+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)2+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 :)
     
  15. Oct 28, 2011 #14

    Mark44

    Staff: Mentor

    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)5 - (n - 1) is divisible by 30."
    NO! You are assuming that "(n - 1)5 - (n -1) is divisible by 30" is a true statement.
    You're misinterpreting what I said.

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

    So the equation to start working on is (n - 1)5 - (n -1) = 30k (for some integer k).
     
    Last edited: Oct 28, 2011
  16. Oct 28, 2011 #15
    @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 "n5-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, 15-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)5-(n-1) = 30k
    (n-1)[(n-1)4-1] = 30k
    (n-1)[(n-1)2-1][(n-1)2+1] = 30k
    (n-1)(n-1-1)(n-1+1)[(n-1)2+1] = 30k
    (n-1)(n-2)(n)[(n-1)2+1] = 30k

    What should I do next?
     
    Last edited: Oct 28, 2011
  17. Oct 28, 2011 #16

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    Try using [itex]n^5-n = [(n-1)+1]^5-[(n-1)+1][/itex]. Expand in terms of (n-1), and then use the induction hypothesis to replace (n-1)5-(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.
     
  18. Oct 29, 2011 #17
    Hi,I'm struggled to expand [itex][(n-1)+1]^5-[(n-1)+1][/itex] in terms of (n-1). Had a few tries all failed. Can you show me how to do it please. Thanks!
     
  19. Oct 29, 2011 #18

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    You use the binomial theorem
    [tex](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.[/tex]or simply multiply out (x+1)5 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*}
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook