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

New to induction, stuck on a proof and i need some help

  1. Jun 7, 2005 #1
    I am trying to prove that 3 divides [tex]n^3~-7n+3[/tex] for all integers n greater than or equal to 0.

    I have gotten to this point:
    Where I try to show that is true for k+1. I have been scribbling on scrap paper trying to figure it out. I've expanded the expression countless times no avail.
    Could someone give me a hint?
  2. jcsd
  3. Jun 7, 2005 #2


    User Avatar
    Science Advisor

    How about multiplying out (k+1)3- 7(k+1)+ 3?
    Part of it, of course, will be k3-7k+ 3 which you know, by the "induction hypothesis", is divisible by 3: k3- 7k+ 3= 3n for some integer n. What is the rest? Can you factor a "3" out of it?
  4. Jun 7, 2005 #3
    Consider n^3-7n+3= n^3-n-6n+3=n(n^2-1)-3(2n-1)=(n-1)n(n+1)-3(2n-1). You just need to prove (by induction) that the product of three consecutive integers ((n-1)n(n+1)) is always divisible by 3 since 3(2n-1) is divisible by 3.
  5. Jun 8, 2005 #4
    Ahhh, I didn't notice that when I was expanding out. The k's threw me off :(
    Question: You expanded -7(k+1). Where is the -7?

    The equation within the brackets is divisible by 3, but -7 is not. I really like this approach because this is more of how I would try to solve the problem. The -7 doesn't make sense though. Maybe I missed something in your explanation.

    Thanks for the help.

    Awesome. This makes sense. I wonder how you are able to see these things right away. Must take a lot of practice to be able to play around with terms that easily. I'll probably give this one a shot, I just feel like I didn't do any work :( Thanks for the help though. :D
  6. Jun 8, 2005 #5


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Recheck that. The part within brackets is not divisible by 3. You must multiply out the cubic term and keep only the k^3 part within the brackets. The rest go outside, by the "-7".
  7. Jun 8, 2005 #6
    Isn't it though? By the induction hypothesis I am assuming that P(n) is true, that is 3 divides n3-7k+3 where n is just k+1.
  8. Jun 8, 2005 #7
    Whoops, ignore my previous post. :D
  9. Jun 19, 2005 #8


    User Avatar

    I have an easy prove for you, but is not quite sure if I'm making an illegal conclusion (I have not learned about induction yet). Take a look:

    First I asume that 3|(n^3 - 7n + 3) is true. Then I try to prove that 3|((n+1)^3 - 7(n+1) + 3) is also true...

    I do this by expanding the expresion to:
    n^3 + 3n^2 + 3n + 1 - 7n - 7 + 3

    And move the terms around:
    (n^3 - 7n + 3) + (3n^2 + 3n + 1 - 7)

    And at last simplify it:
    (n^3 - 7n + 3) + (3n^2 + 3n - 6)
    (n^3 - 7n + 3) + 3*(n^2 + n - 2)

    Since 3*(n^2 + n - 2) is divisible with 3, I have proven that if 3|(n^3 - 7n + 3) is true, then 3|((n+1)^3 - 7(n+1) + 3) is also true! I guess that is what induction is all about?
  10. Jun 28, 2005 #9
    if n^3-7n+3 is divisible by 3 then isnt
    n^3-7n is divisible by 3?

    n^3-7n= n(n^2-7)
    if n is not divisible by 3, then n^2-7 must. when 3 is in, n^2-7 is never divisible by 3, always a remainder of 2. n^2-7= n^2-4-3

    (n-2)(n+2)-3 must be divisible by 3 when n is not divisible by 3.
    the three at the end cancels because we know that if k is divisible by 3, then so is k-3.
    (n-2)(n+2) must be divisible by 3.
    If n has a remainder of 1, like 4, then n+2 must be divisible by 3. If n has a remainder of 2, then (n-2) must be divisible by 3. And the maximum remainder you could possibly have is 2.
    Last edited: Jun 28, 2005
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook