Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Induction proof

  1. Jul 14, 2011 #1
    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. jcsd
  3. Jul 15, 2011 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  4. Jul 15, 2011 #3

    HallsofIvy

    User Avatar
    Science Advisor

    How can you factor [itex]n^3- n[/itex]?
     
  5. Jul 15, 2011 #4
    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
     
  6. Jul 15, 2011 #5
    Take n=3, what is the largest proper divisor of n3-n then?
     
  7. Jul 15, 2011 #6
    would it be 12...which is not n^2-1
     
  8. Jul 15, 2011 #7
    But which is the half of n3-n. Can you show that the half is always the largest divisor??
     
  9. Jul 15, 2011 #8
    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
     
  10. Jul 15, 2011 #9
    Isn't it obvious that [itex]\frac{n^3-n}{2}[/itex] 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.
     
  11. Jul 15, 2011 #10
    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?
     
  12. Jul 15, 2011 #11
    Indeed, you must show that [itex](n+1)^3-(n+1)[/itex] is even when [itex]n^3-n[/itex] is.
     
  13. Jul 15, 2011 #12
    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.
     
  14. Jul 15, 2011 #13

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Hi Punkyc7! :smile:
    Doesn't it mean find the highest common factor of every value of n3 - n ? :confused:
     
  15. Jul 15, 2011 #14
    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
     
  16. Jul 15, 2011 #15

    hunt_mat

    User Avatar
    Homework Helper

    [itex]n^{3}-n=n(n^{2}-1)=(n-1)n(n+1)[/itex]
     
  17. Jul 15, 2011 #16
    ok, so how is knowing the roots helpful?
     
  18. Jul 16, 2011 #17

    Char. Limit

    User Avatar
    Gold Member

    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?)
     
  19. Jul 16, 2011 #18
    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
     
  20. Jul 16, 2011 #19

    Char. Limit

    User Avatar
    Gold Member

    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?
     
  21. Jul 16, 2011 #20
    I want to say yes
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted