1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Simple proof of inequality by induction

  1. Oct 12, 2009 #1
    1. The problem statement, all variables and given/known data
    Prove [tex]2n+1< 2^n[/tex] for n=3,4,...


    2. Relevant equations



    3. The attempt at a solution
    [tex]
    P(3)= 6+1<2^3
    [/tex]
    The base case holds, now assume true for [itex]P(k)[/itex]. Now consider [itex]P(k+1)[/itex]
    [tex]
    2(k+1) +1 = 2k+3 [/tex]
    [tex]
    2^{k+1} = 2^k \cdot 2
    [/tex]

    So this is where I get stuck, I don't quite know how to finish the proof. As can be seen, the difference between the two sides of the inequality in P(k+1) is that the LHS has 2 added, while the RHS is multiplied by 2. Would it be sufficient to observe that in the base case, adding 2 to the LHS and multiplying the RHS by 2 still maintains the inequality and so necessarily it should hold for any larger n?
     
  2. jcsd
  3. Oct 12, 2009 #2

    lanedance

    User Avatar
    Homework Helper

    2(k+1) +1 = 2k+3 = (2k+1) + 1
    2^{k+1} = 2.2^k

    so starting with the case for n
    2n+1<2n

    add 2 to both sides
    2(n+1)+1<2n+2

    with one more step to show the case for n+1
     
  4. Oct 12, 2009 #3
    Well, it should be possible to show that [itex]2^k+2<2^k \cdot 2[/itex] for some k greater than whatever.

    [tex]2< 2\cdot 2^k - 2^k[/tex]
    [tex]2< (2-1)2^k[/tex]
    [tex]2<2^k[/tex]. From here take the log of both sides, and it shows that [tex]2^k +2 < 2^{k+1}[/tex] holds for all k > 1, which is fine because we're only considering from n=3. So since that's the case and [tex]2(n+1)+1 < 2^n +2 < 2^{n+1}[/tex] this should complete the proof?
     
  5. Oct 13, 2009 #4

    lanedance

    User Avatar
    Homework Helper

    i think that does it, but if you're happy upto
    2(n+1)+1<2n+2

    then just using, that for n>1
    2<2n

    should pretty much complete above

    ps. i think itspretty much the same reasoning, though just a little clearer in order
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Simple proof of inequality by induction
Loading...