- #1
naele
- 202
- 1
Homework Statement
Prove [tex]2n+1< 2^n[/tex] for n=3,4,...
Homework Equations
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?