Simple proof of inequality by induction

[naele]

Homework Statement

Prove 2n+1< 2^n for n=3,4,...

Homework Equations

The Attempt at a Solution

<br /> P(3)= 6+1&lt;2^3<br />
The base case holds, now assume true for P(k). Now consider P(k+1)
<br /> 2(k+1) +1 = 2k+3
<br /> 2^{k+1} = 2^k \cdot 2<br />

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?

 

[lanedance]

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

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

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

with one more step to show the case for n+1

 

[naele]

Well, it should be possible to show that 2^k+2&lt;2^k \cdot 2 for some k greater than whatever.

2&lt; 2\cdot 2^k - 2^k
2&lt; (2-1)2^k
2&lt;2^k. From here take the log of both sides, and it shows that 2^k +2 &lt; 2^{k+1} holds for all k > 1, which is fine because we're only considering from n=3. So since that's the case and 2(n+1)+1 &lt; 2^n +2 &lt; 2^{n+1} this should complete the proof?

 

[lanedance]

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

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

should pretty much complete above

ps. i think itspretty much the same reasoning, though just a little clearer in order