Results 1 to 4 of 4

Math Help - Mathematical Induction

  1. #1
    Newbie
    Joined
    Aug 2007
    Posts
    10

    Mathematical Induction

    - If n is a positive odd integer, show that n^2+3 is divisible by 4 ~ dont know whether to do this by congruence or mathematical induction
    - Use mathematical induction to prove that 3|(n^3-4n+6) for all positive integers n
    Any help is appreciated!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,738
    Thanks
    644
    Hello, Jacko!

    If n is a positive odd integer, show that n^2+3 is divisible by 4
    If you don't have to use induction, an algebraic proof is faster.


    Let n \:=\:2a-1 for some positive integer a.

    Then: . n^2+3\;=\;(2a-1)^2 + 3 \;=\;4a^2 + 4a + 1 + 3\;=\;4a^2 + 4a + 4 \;=\;4(a^2 + a + 1)

    Therefore: . n^2 + 3 is divisible by 4.



    Use induction to prove: . 3|(n^3-4n+6) for all positive integers n

    S(1)\!:\;1^3 - 4\cdot1 + 6 \:=\:3 . . . yes!


    Assume S(k)\!:\;\;k^3 - 4k + 6 \:=\:3m .for some integer m

    Add 3k^2 + 3k + 1 to both sides:
    . . k^3 \,{\color{blue}+\, 3k^2 + 3k + 1}\, - 4k + 6 \:=\:3m\, {\color{blue}+\, 3k^2 + 3k + 1}

    Subtract 4 from both sides:
    . (k+1)^3 - 4k \,{\color{blue}- \,4} + 6 \:=\:3m + 3k^2 + 3k + 1 \,{\color{blue}- \,4}

    And we have: . (k+1)^3 - 4(k+1) + 6 \:=\:3(m + k^2 + k - 1)


    The left side is the left side of S(k\!+\!1)
    The right side is divisible by 3.

    The inductive proof is complete.

    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2007
    Posts
    10
    Thank you so much Soroban!!
    I just have one question, why do you add 3k^2+3k+1 to both sides in the inductive question?
    Thanks again!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,939
    Thanks
    338
    Awards
    1
    Quote Originally Posted by Jacko View Post
    Thank you so much Soroban!!
    I just have one question, why do you add 3k^2+3k+1 to both sides in the inductive question?
    Thanks again!
    He's trying to make the k^3 term go to (k + 1)^3.

    Here's a slightly different way:
    We wish to show that 3 divides n^3 - 4n + 6 for all (positive integer) values of n.

    So try n = 0: 0^3 - 4 \cdot 0 + 6 = 6
    This is divisible by 3, so the theorem is true for this case.

    So now assume the theorem is true for some n = k. We wish to show the theorem is also true for n = k + 1.

    So we need to show that 3 divides (k + 1)^3 - 4(k + 1) + 6 given that 3 divides k^3 - 4k + 6.

    So look at (k + 1)^3 - 4(k + 1) + 6:
    (k + 1)^3 - 4(k + 1) + 6

    = (k^3 + 3k^2 + 3k + 1) - (4k + 4) + 6

    = k^3 + 3k^2 + 3k + 1 - 4k - 4 + 6

    = k^3 + 3k^2 - k + 3

    Now, I want to make this expression a bit simpler by reducing the number of terms in it. One way to do this is to subtract out a multiple of 3. (If we can show that a number "a - 3m" is divisible by 3 then we will have shown that "a" is also divisible by 3.)

    One handy thing to know about using Mathematical Induction is that the theorem itself that we are trying to prove comes in handy. We know that k^3 - 4k + 6 is divisible by 3 (that's our assumption.) So I'm going to subtract this from our other expression. If the result is divisible by 3, then so is our original expression.
    (k^3 + 3k^2 - k + 3) - (k^3 - 4k + 6)

    = 3k^2 + 3k - 3 = 3(k^2 + k - 1)

    Since this expression is divisible by 3 then so is
    k^3 + 3k^2 - k + 3 = (k + 1)^3 - 4(k + 1) + 6

    So the theorem is true for n = k + 1. Therefore etc.

    -Dan
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: August 31st 2010, 03:31 PM
  2. Mathematical induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: August 30th 2010, 05:54 AM
  3. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  4. mathematical induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 13th 2009, 05:29 PM
  5. Mathematical Induction
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 18th 2009, 08:35 AM

Search Tags


/mathhelpforum @mathhelpforum