prove $2n+1 < 2^{n}$ by induction

Question

true for base case $n = 3$, and assume true for $n=k$, then

for $k \geq 3$, $$2k+1 \leq 2^{k}$$ $$2k+1 + 2 \leq 2^{k} +2$$ $$2(k+1) +1 \leq 2^{k} +2$$ since, $2^{k} +2 \leq 2^{k}\cdot2$, (requires another proof?)

then,

$$2(k+1) +1 \leq 2^{k} +2 \leq 2^{k}*2$$ $$2(k+1) +1 \leq 2^{k+1}$$

but i think i have to prove the since part $2^{k} +2 \leq 2^{k}\cdot2$, another proof to prove in this proof?

$2=2^1<2^k$ so $2^k+2<2^k+2^k$. – vadim123 Mar 06 '18 at 02:37 — vadim123, Mar 06 '18 at 02:37
Yes, but also you have to pay attention to $\le$ vs $\lt$. – NickD Mar 06 '18 at 02:38 — NickD, Mar 06 '18 at 02:38

score 2 · Answer 1 · answered Mar 06 '18 at 03:05

2

You do not need another proof.

$$2(k+1) +1 \leq 2^{k} +2< 2^{k}+2^{k}=2^{k+1}$$

answered Mar 06 '18 at 03:05

Mohammad Riazi-Kermani

68,728

score 1 · Answer 2 · answered Mar 06 '18 at 02:42

You should try to do this in one proof. You got to $2k+1+2 < 2^k + 2 \le 2^{k+1}$ and you're wondering what you have to do to show that $2^k + 2 \le 2^{k+1}$, which would complete your proof. See that subtracting $2^k$ from both sides gives you $2 \le 2^k$, which you know is true since $k \ge 3$. No need for another induction proof.

score 1 · Answer 3 · answered Mar 06 '18 at 02:59

You are trying to prove $2n+1 < 2^n$. So I think you should set your induction case to be assume $2k+1 < 2^k$, there should be a strict inequality. Next, what you did was correct, you have $2(k+1)+1 < 2^k+2$. Since $2^{k+1}=2^k+2^k$ and $2^k>=8>2$. You should have $2(k+1)+1 < 2^k+2<2^{k+1}$. No need for another proof. You are done.

prove $2n+1 < 2^{n}$ by induction

3 Answers3