Results 1 to 12 of 12

Math Help - mathematical induction

  1. #1
    Senior Member polymerase's Avatar
    Joined
    May 2007
    From
    Sydney
    Posts
    267

    mathematical induction

    how do I prove the following for all postive integers n

    3^(3n) + 2^(n+2) is divisible by 5
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,927
    Thanks
    333
    Awards
    1
    Quote Originally Posted by polymerase View Post
    how do I prove the following for all postive integers n

    3^(3n) + 2^(n+2) is divisible by 5
    3/5 leaves a "remainder" of -2 upon division. (In more complicated "mathspeak" this means 3 \equiv -2 (mod 5).)

    Thus 3^x is going to leave a remainder of (-2)^x after division, where x is a positive integer. ( 3^x \equiv (-2)^x (mod 5).)

    And
    (-2)^{3n} = (-1)^{3n}2^{3n} = (-1)^n2^{3n}

    Now, 2^{n + 2} = 4 \cdot 2^n.

    4/5 leaves a remainder of -1 upon division ( 4 \equiv -1 (mod 5)), so 4 \cdot 2^n leaves a remainder of -1 \cdot 2^n.

    So. Let's finally take a look at this.
    3^{3n} + 2^{n+2} divided by 5 will leave a remainder of
    (-1)^n2^{3n} - 2^n = 2^n \left ( (-1)^n2^{2n} - 1 \right )

    Let's do this case by case.

    If n is even then
    (-1)^n2^{2n} - 1 = 2^{2n} - 1

     = \left ( 2^n \right ) ^2 - 1^2 = (2^n + 1)(2^n - 1)

    If n is doubly even (ie n = 4x) then 2^n - 1 = 2^{4x} - 1 = 16^x - 1.
    Now, 16 leaves a remainder of 1 upon division by 5, so
    16^x - 1 leaves a remainder of 1^x - 1 = 0 upon division by 5. So 2^n - 1 is divisible by 5 if n is doubly even.

    If n is even, but not doubly even then n = 4x + 2. Then
    2^n + 1 = 2^{4x + 2} + 1 = 4 \cdot 2^{4x} + 1

     = 4 \cdot 16^x + 1
    Dividing this by 5 leaves a remainder of -1 \cdot 1^x + 1 = -1 + 1 = 0. So 2^n + 1 is divisible by 5 if n is even but not doubly even.

    Thus 3^{3n} + 2^{n+2} is divisible by 5 if n is even.

    If n is odd then n = 2x + 1:
    (-1)^n2^{2n} - 1 = -(2^{2n} + 1)

     = -(2^{2(2x + 1)} + 1) = -(2^{4x + 2} + 1)

     = -(4 \cdot 2^{4x} + 1) = -(4\cdot 16^x + 1)

    As in the last case (where n was even but not doubly even) 4 \cdodt 16^x + 1 is divisible by 5.

    Thus 3^{3n} + 2^{n+2} is divisible by 5 if n is odd.

    Thus 3^{3n} + 2^{n+2} is divisible by 5 for all n.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,927
    Thanks
    333
    Awards
    1
    Quote Originally Posted by polymerase View Post
    how do I prove the following for all postive integers n

    3^(3n) + 2^(n+2) is divisible by 5
    Ah, okay. I just noticed that the title of the original post is "mathematical induction." So let's try this:

    n = 0:
    3^{3 \cdot 0} + 2^{0 + 2} = 3^0 + 2^2 = 1 + 4 = 5
    is manifestly divisible by 5.

    Now assume that the statement is true for some given value of n. We wish to show it is true for n + 1.

    3^{3(n + 1)} + 2^{(n + 1) + 2} = 3^{3n + 3} + 2^{n + 3} = 27 \cdot 3^{3n} + 2 \cdot 2^{n + 2}

    Now let 5x = 3^{3n} + 2^{n + 2}, so according to our supposition x is a whole number. Then
    3^{3n} = \left ( 5x - 2^{n + 2} \right )

    So
    3^{3(n + 1)} + 2^{(n + 1) + 2} = 27 \left ( 5x - 2^{n + 2} \right ) + 2 \cdot 2^{n + 2}

     = 27 \cdot 5x - 27 \cdot 2^{n + 2} + 2 \cdot 2^{n + 2} = 27 \cdot 5x + (-27 + 2) 2^{n + 2}

     = 27 \cdot 5x - 25 \cdot 2^{n + 2}

    As both terms are multiples of 5, so is the difference.

    Thus the theorem is also true for n + 1 if it is true for some n.

    Since it is true for n = 0, it is true for n = 1, thus also for n = 2, etc.

    (This is not only faster than my previous method, but easier to understand. )

    -Dan
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Bar0n janvdl's Avatar
    Joined
    Apr 2007
    From
    Meh
    Posts
    1,630
    Thanks
    6
    So basically to prove this we only insert values for n?

    But that doesnt seem right. I dont think it will always work just because it worked in a few circumstances.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,927
    Thanks
    333
    Awards
    1
    Quote Originally Posted by janvdl View Post
    So basically to prove this we only insert values for n?

    But that doesnt seem right. I dont think it will always work just because it worked in a few circumstances.
    You find one specific value of n that works, then show that the theorem works for n + 1 also. (Which then implies it works for all whole numbers greater than or equal to n by the Principle of Mathematical Induction.)

    -Dan
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Bar0n janvdl's Avatar
    Joined
    Apr 2007
    From
    Meh
    Posts
    1,630
    Thanks
    6
    Quote Originally Posted by topsquark View Post
    You find one specific value of n that works, then show that the theorem works for n + 1 also. (Which then implies it works for all whole numbers greater than or equal to n by the Principle of Mathematical Induction.)

    -Dan
    Oh ok. Would you mind giving me the Principle of Mathematical Induction? And maybe a very short explanation? Or does it just involve substituting n with values?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,927
    Thanks
    333
    Awards
    1
    Try this for starters. There are a variety of examples on this site and the web in general.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,735
    Thanks
    642
    Hello, polymerase!

    Prove by induction: . 3^{3n} + 2^{n+2} is divisible by 5.
    Verify S(1)

    . . 3^3 + 2^3\:=\:27 + 8 \:=\:35 . . . true!


    Assume S(k) is true

    . . 3^{3k} + 2^{k+2} \;=\;5a for some integer a. . [1]


    We want to show that: . 3^{3k+3} + 2^{k+3} is divisible by 5.


    Add 26\!\cdot\!3^{3k} + 2^{k+2} to both sides of [1]

    . . 3^{3k} + 26\!\cdot\!3^{3k} + 2^{k+2} + 2^{k+2} \;= \;5a + 26\!\cdot\!3^{3k} + 2^{k+2}


    We have: . 27\!\cdot\!3^{3k} + 2\!\cdot\!2^{k+2} \;= \;5a + 25\!\cdot\!3^{3k} + 3^{3k} + 2^{k+2}

    . . . . . . . . . 3^3\!\cdot\!3^{3l} + 2^{k+3} \;=\;\left(5a + 25\cdot3^{3k}\right) + \underbrace{\left(3^{3k} + 2^{k+2}\right)}_{\text{This is }5a}

    . . . . . . . . . 3^{3k+3} + 2^{k+3} \;=\;10a + 25\!\cdot\!3^{3k} \;=\;5\left(2a + 5\!\cdot\!3^{3k}\right)


    Therefore: . 3^{3k+3} + 2^{k+3} is divisible by 5.

    The inductive proof is complete.
    .
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,927
    Thanks
    333
    Awards
    1
    Quote Originally Posted by ThePerfectHacker View Post
    What does this have to do with Mathematical Induction? I'm afraid you've lost me.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  11. #11
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by topsquark View Post
    What does this have to do with Mathematical Induction? I'm afraid you've lost me.

    -Dan
    induction is used in the fifth post on the page, the post by TPH that starts off talking about the Well-Ordered principle. it's hard to relate the specific example to the problem here, but it may serve as a model of how induction is used
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,927
    Thanks
    333
    Awards
    1
    Quote Originally Posted by Jhevon View Post
    induction is used in the fifth post on the page, the post by TPH that starts off talking about the Well-Ordered principle
    Ah! Thank you.

    -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