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

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

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<2^k \cdot 2$ for some k greater than whatever.

$$2< 2\cdot 2^k - 2^k$$
$$2< (2-1)2^k$$
$$2<2^k$$. From here take the log of both sides, and it shows that $$2^k +2 < 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 < 2^n +2 < 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