Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question already has an answer here:

I struggle to proof that:

$2n+1<2^n$

By using induction.

The base case is for $n\ge3$.

Any help will be appreciated!

share|improve this question

marked as duplicate by anorton, baba ji, hardmath, Hakim, M Turgeon Jul 18 at 18:47

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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

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

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.