Results 1 to 4 of 4

Math Help - Proof by induction

  1. #1
    Newbie
    Joined
    Dec 2010
    Posts
    4

    Proof by induction

    Hello again,
    I was helped nicely on the other question that I posted that I thought I'd post another--but this one is more to be checked over rather than one that needs complete guidance on...

    The question is: Prove: for all integers n >= 0, 3|(n^3-7n+3) by induction.

    Obviously, the base step I have is that with n=0, 0^3 - 7(0) + 3 = 3 and 3|3 since 3 mod 3=0 and thus 3 divides 3. Therefore the base step is proven.

    For the inductive step, I am substituting P(n) with P(n+1) and therefore I have (n+1)^3 - 7(n+1) + 3 and, through some algebraic manipulation, I can get (n^3 - 7n + 3) + 3n^2 + 3n + 6. Now my question is: can I finish this proof off by saying that if (n^3 - 7n + 3) (the base step) is obviously divisible by three, the total in the inductive step (that is when you add 3n^2 + 3n + 6 to (n^3 - 7n + 3)) is also divisible by 3 since (3n^2 + 3n + 6) is just a bunch of additions of multiples of 3? Or is there a better way to end this? Thanks in advance!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Dec 2009
    From
    1111
    Posts
    872
    Thanks
    3
    Quote Originally Posted by JTL4869 View Post
    Hello again,
    I was helped nicely on the other question that I posted that I thought I'd post another--but this one is more to be checked over rather than one that needs complete guidance on...

    The question is: Prove: for all integers n >= 0, 3|(n^3-7n+3) by induction.

    Obviously, the base step I have is that with n=0, 0^3 - 7(0) + 3 = 3 and 3|3 since 3 mod 3=0 and thus 3 divides 3. Therefore the base step is proven.

    For the inductive step, I am substituting P(n) with P(n+1) and therefore I have (n+1)^3 - 7(n+1) + 3 and, through some algebraic manipulation, I can get (n^3 - 7n + 3) + 3n^2 + 3n + 6. Now my question is: can I finish this proof off by saying that if (n^3 - 7n + 3) (the base step) is obviously divisible by three, the total in the inductive step (that is when you add 3n^2 + 3n + 6 to (n^3 - 7n + 3)) is also divisible by 3 since (3n^2 + 3n + 6) is just a bunch of additions of multiples of 3? Or is there a better way to end this? Thanks in advance!
    Dear JTL4869,

    Yes your reasoning is correct.

    If n^3-7n+3 is divisible by 3, n^3-7n+3=3k~where~k\in Z. Hence (n^3 - 7n + 3) + 3n^2 + 3n + 6=3k+3n^2 + 3n + 6=3(k+n^2+n+2)

    Since n and k are integers, k+n^2+n+2 is also an integer. Therfore, 3(k+n^2+n+2) is divisible by 3.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Double check your work...

    Should you have a +6 or a -6 ?

    Doesn't make any difference to the proof ... but
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Dec 2010
    Posts
    4
    Quote Originally Posted by Archie Meade View Post
    Double check your work...

    Should you have a +6 or a -6 ?

    Doesn't make any difference to the proof ... but
    Woops! You're right.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by induction that 4| 5^n - 1
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 17th 2010, 11:23 AM
  2. proof by induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 17th 2010, 08:11 AM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 10:33 PM
  4. induction proof
    Posted in the Algebra Forum
    Replies: 7
    Last Post: November 1st 2008, 05:32 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 02:20 PM

Search Tags


/mathhelpforum @mathhelpforum