Results 1 to 11 of 11

Math Help - Prove by Mathematical Induction

  1. #1
    Newbie
    Joined
    Jun 2007
    Posts
    3

    Prove by Mathematical Induction

    Hi everyone I need a little help, Im stuck.

    I have to prove by induction that:

    <br />
2^{n+2} + 3^{2n+1}<br />

    is exactly divisible by 7 for all positive integers of n.

    Now what I have done is:

    1)

    If 2^{n+2} + 3^{2n+1} is divisible by 7

    =>( 2^{n+2} + 3^{2n+1}=7a )-----> Pn statement

    where a is a positive integer

    2) P_1 statement where n=1

    =>
    LHS: 2^{1+2} + 3^{2(1)+1} = 35
    RHS: 7(5) = 35

    Therefore P_1 is true.


    3) Assuming P_k to be true where n=k

    => P_k = 2^{k+2} + 3^{2k+1} = 7a


    4) Therefore

     P_{k+1} = 2^{(K+1)+2} + 3^{2(k+1)+1}

    Now here is where Im stuck, Im not getting to factor out a 7 i.e.
    getting 7(some integer) to prove that P_{k+1} is divisible by 7.

    Any help would be greately appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    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 princemac View Post
    Hi everyone I need a little help, Im stuck.

    I have to prove by induction that:

    <br />
2^{n+2} + 3^{2n+1}<br />

    is exactly divisible by 7 for all positive integers of n.

    Now what I have done is:

    1)

    If 2^{n+2} + 3^{2n+1} is divisible by 7

    =>( 2^{n+2} + 3^{2n+1}=7a )-----> Pn statement

    where a is a positive integer

    2) P_1 statement where n=1

    =>
    LHS: 2^{1+2} + 3^{2(1)+1} = 35
    RHS: 7(5) = 35

    Therefore P_1 is true.


    3) Assuming P_k to be true where n=k

    => P_k = 2^{k+2} + 3^{2k+1} = 7a


    4) Therefore

     P_{k+1} = 2^{(K+1)+2} + 3^{2(k+1)+1}

    Now here is where Im stuck, Im not getting to factor out a 7 i.e.
    getting 7(some integer) to prove that P_{k+1} is divisible by 7.

    Any help would be greately appreciated.
    for (4), we will do a trick often used in math--add zero in a weird way, that way we don't change anything, but are able to factor things in a convenient way.

    P(k+1): 2^{k+3} + 3^{2k + 3} = 2^{k + 3} \underbrace { + 2 \cdot 3^{2k + 1} - 2 \cdot 3^{2k + 1} } + 3^{2k + 3}

    Note that what is underbraced is zero

    = 2 \left( 2^{k + 2} + 3^{2k + 1} \right) - 3^{2k + 1} \left(  2 - 3^2\right)

    = 2 \cdot 7a + 7 \cdot 3^{2k + 1}

    = 7 \left( 2a + 3^{2k + 1} \right)

    which is divisible by 7
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jun 2007
    Posts
    3
    Ahhh many thanks, now that Ive seen what you did I can see another way.

    P_{k+1}= 2^{k+3} + 3^{2k + 3} = (2)(2^{k+2}) + (9)3^{2k + 1}<br />

    2^{k+2}= 7a - 3^{2k + 1}

    Therefore
    P_{k+1} = 14a + 3^{2k + 1}(9 -2)= 7(2a + 3^{2k+1})

    Thats pretty cool with the zero, I'll have to remeber that.
    Thanks again.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    earboth's Avatar
    Joined
    Jan 2006
    From
    Germany
    Posts
    5,829
    Thanks
    123
    Quote Originally Posted by princemac View Post
    Hi everyone I need a little help, Im stuck.

    I have to prove by induction that:

    <br />
2^{n+2} + 3^{2n+1}<br />

    is exactly divisible by 7 for all positive integers of n.

    Now what I have done is:

    1)

    If 2^{n+2} + 3^{2n+1} is divisible by 7

    =>( 2^{n+2} + 3^{2n+1}=7a )-----> Pn statement

    where a is a positive integer

    2) P_1 statement where n=1

    =>
    LHS: 2^{1+2} + 3^{2(1)+1} = 35
    RHS: 7(5) = 35

    Therefore P_1 is true.


    3) Assuming P_k to be true where n=k

    => P_k = 2^{k+2} + 3^{2k+1} = 7a


    4) Therefore

     P_{k+1} = 2^{(K+1)+2} + 3^{2(k+1)+1}

    Now here is where Im stuck, Im not getting to factor out a 7 i.e.
    getting 7(some integer) to prove that P_{k+1} is divisible by 7.

    Any help would be greately appreciated.
    Hello,

    I take over your result and transform it a little bit:

     P_{k+1} = 2^{(K+1)+2} + 3^{2(k+1)+1} =
    2 \cdot 2^{k+2} + 9 \cdot 3^{2k+1} =
    2^{k+2} + 2^{k+2} + 3^{2k+1} + 3^{2k+1} + 7 \cdot 3^{2k+1} rearrange the summands:

    \underbrace{2^{k+2} + 3^{2k+1}}_{\text{divisible by 7}} + \underbrace{2^{k+2} + 3^{2k+1}}_{\text{divisible by 7}} + \underbrace{7 \cdot  3^{2k+1}}_{\text{divisible by 7}}
    Follow Math Help Forum on Facebook and Google+

  5. #5
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    once again, it seems i was thinking too hard. both your methods seem nicer than mine for some reason
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Jhevon View Post
    once again, it seems i was thinking too hard. both your methods seem nicer than mine for some reason
    Disagree, yours seems more elegant to me.

    RonL
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,615
    Thanks
    1578
    Awards
    1
    Quote Originally Posted by Jhevon View Post
    once again, it seems i was thinking too hard. both your methods seem nicer than mine for some reason
    Quote Originally Posted by CaptainBlack View Post
    Disagree, yours seems more elegant to me.
    RonL
    I am with the Captain all the way on this one!
    Jhevon, yours is the preferred way because it is easier to remember after one has done several of these.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,710
    Thanks
    629
    Hello, princemac!

    I have to prove by induction that:
    2^{n+2} + 3^{2n+1} is divisible by 7 for all positive integers n.

    Your work is correct . . .

    Verify P(1):\;\;2^{k+2} + 3^{2\cdot1+1} \:= \:35 . . . True!

    Assume P(k) is true: . 2^{k+2} + 3^{2k+1} \:= \:7a .for some integer a.

    We want to prove P(k+1):\;2^{k+3} + 3^{2k + 3} \:=\:7b .for some integer b.
    [I like to write this statement now, so I know what I'm aiming for.]


    Begin with P(k):\;2^{k+2} + 3^{2k+1} \:=\:7a


    Add 2^{k+2} + 8\!\cdot\!3^{2k+1} to both sides:

    . . \underbrace{2^{k+2} + 2^{k+2}} + \underbrace{3^{2k+1} + 8\!\cdot\!3^{2k+1}} \;=\;7a + 2^{k+2} + 8\!\cdot\!3^{2k+1}

    - . - 2\!\cdot\!2^{k+2} \quad+ \quad(1 + 8)\!\cdot\!3^{2k+1} \;= \;7a + \underbrace{2^{k+2} + 3^{2k+1}}_{\text{this is }7a} + 7\!\cdot\!3^{2k+1}

    . . . . . . . . . . 2^{k+3} \;+ \;9\!\cdot\!3^{2k+1} \;=\;7a + 7a + 7\!\cdot\!3^{2k+1}

    . - . . - . . . . . 2^{k+3} + 3^2\!\cdot\!3^{2k+1} \;=\;14a + 7\!\cdot\!3^{2k+1}

    . . . . . . . . . . . 2^{k+3} + 3^{2k+3} \;=\;7\underbrace{(2a + 3^{2k+1})}_{\text{This is an integer}}

    Therefore: . . . 2^{k+3} + 3^{2k+3} \;=\;7b

    We have proved P(k+1) . . . The inductive proof is complete.

    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,615
    Thanks
    1578
    Awards
    1
    Is it a general rule that one should read the entire thread before responding?
    If not, there ought to be such a rule!
    Is the pervious post in this thread a case in my point?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,710
    Thanks
    629
    Absolutely right, Plato!

    Guilty as charged . . .

    I thought I read through the posts (evidently not)
    . . and thought I had something original to offer (wrong again).
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,615
    Thanks
    1578
    Awards
    1
    Thank you for that.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  2. Prove By Mathematical Induction
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: May 30th 2010, 10:22 AM
  3. using mathematical induction to prove..
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 12th 2009, 08:28 AM
  4. using mathematical induction to prove something
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: April 30th 2008, 07:32 PM
  5. Prove by Mathematical Induction
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 17th 2007, 10:29 AM

Search Tags


/mathhelpforum @mathhelpforum