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:
    [tex]3|(k~+~1)^3~-~7(k~+~1)~+~3[/tex]
    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

    HallsofIvy

    User Avatar
    Staff Emeritus
    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?

    [tex][(k+1)^3-7k+3]-7[/tex]
    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

    Gokul43201

    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

    HAP

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

Have something to add?



Similar Discussions: New to induction, stuck on a proof and i need some help
Loading...