Take the 2-minute tour ×

This question already has an answer here:

I struggle to proof that:


By using induction.

The base case is for $n\ge3$.

Any help will be appreciated!

share|improve this question

marked as duplicate by anorton, This is much healthier., hardmath, Hakim, M Turgeon Jul 18 at 18:47


Somewhat similar question Prove that $ n < 2^{n}$ for all natural numbers $n$. –  Martin Sleziak Sep 7 '13 at 11:20
add comment

2 Answers 2

up vote 3 down vote accepted

First show $P(3)$.

Now, assume the truth of $2k+1<2^k$ for some $k\in \mathbb{N}\setminus\{1,2\}$. We want to show $2(k+1)+1<2^{k+1}$.

Multiply the hypothesis by $2$ to obtain, $2\cdot(2k+1)<2^{k+1}$ and note that $2(k+1)+1=2k+2+1<2k+2+2k=4k+2$.

share|improve this answer
add comment

Let $P(n): 2^n>2n+1$

So, for $n=2,2^2=4,2\cdot2+1=5$ so $P(2)$ is false

For $n=3,2^3=8,2\cdot3+1=7\implies P(n)$ is true for $n=3$

Let $P(n)$ for $n=m\implies 2^m>2m+1$

$\implies 2^{m+1}=2(2^m)>2(2m+1)=4m+2$

For $P(m+1)$ to be true, we need $2^{m+1}>2(m+1)+1=2m+3$

So, it is sufficient to prove $4m+2>2(m+1)+1$

which is true if $2m>1\iff m\ge1$

share|improve this answer
add comment
