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!

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
    Staff Emeritus
    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

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

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

Have something to add?
Draft saved Draft deleted



Similar Discussions: Induction proof
  1. Proof by induction (Replies: 2)

  2. Proof by induction (Replies: 9)

  3. Proof by induction (Replies: 32)

  4. Induction Proof (Replies: 14)

  5. Proof by Induction (Replies: 6)

Loading...