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.

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
    
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

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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