Use induction to prove $2n + 1 \le 2^n$ for $n=3,4,\ldots$

Question

Use induction to prove $2n + 1 \le 2^n$ for $n=3,4,\ldots$

I've plugged $3$ in for $n$ I get $7 \le 8$

then I set $2(n+1) +1 \le 2^{n+1}$

then I'm lost.

Answer 1

We want to show that if $2k+1\le 2^k$ for a particular integer $k\ge 3$, then $2(k+1)+1\le 2^{k+1}$.

We have $2(k+1)+1=2k+1 +2$. By the induction hypothesis, $2k+1\le 2^k$, and therefore $2k+1+2 \le 2^k+2$.

But if $k\ge 1$, then $2^k+2\le 2^k+2^k=2^{k+1}$, so we are finished.

Answer 2

As part of the induction steps you have to assume: $$2n+1\le 2^n$$ And then use that to prove: $$2(n+1)+1\le 2^{n+1}$$

To do this, multiply the induction assumption by $2$, to get: $$4n+4\le 2^{n+1}$$ Since $2n+3<4n+4$, you have completed the proof.

Answer 3

Hint $\ $ If $\, \color{#c00}{f_n} = 2^n-2n-1 > 0\,$ then $\,\color{#0a0}{f_{n+1}\!-f_n} = 2^n\! -2 > 0\,$ for $\,n\ge 2,\,$ so adding them we deduce $\,\color{#0a0}{f_{n+1}\!-f_n} + \color{#c00}{f_n} = f_{n+1}\! > 0,\,$ being a sum of $\rm\color{#0a0}{two}\ \color{#c00}{terms}\, > 0.\,$ This is the inductive step.

Remark $\ $ This can be viewed as a special case of telescopic induction, a powerful method that serves to unify and simplify such forms of induction. Namely, telescopy shows that $\,f_n\,$ is the sum of its differences $\,\color{#0a0}{f_{n}-f_{n-1}}$ which, by above, are positive, hence so to is $\,f_n.$ Thus telescopy reduces the induction to the trivial induction that a sum of positives remains positive. In the same way, telescopy trivializes many inductive proofs involving sums and products, and lends great insight into the essence of such inductive proofs. You can find many further examples in my prior posts on telescopy.