Use mathematical induction to prove that for all integers $n \geq 3,\, 2n + 1 < 2^{n}$

Question

This is what I've got so far.

Let $P(n)$ be the statement that $2n + 1 < 2^n$

Basis:

Let $n = 3$. Show that $P(3)$ is true.

$2(3) + 1 = 7$ and $2^3 = 8$.

Since $7 < 8$, $P(3)$ is true.

Inductive Hypothesis:

Suppose that $P(k)$ is true for an arbitrary integer $k\ge 3$.
This implies that $2k + 1 < 2^k$.

Show that $2(k + 1) + 1 < 2^{k + 1}$.

\begin{align*} 2(k + 1) + 1 &= 2k + 2 + 1\\ &= (2k + 1) + 2 \end{align*}

From the IH,

\begin{align*} 2k + 1 < 2^k &\Rightarrow (2k + 1) + 2 < 2^k + 2\\ &\Rightarrow (2k + 1) + 2 < 2^k + 2 \\ &\Rightarrow (2k + 2) + 1 < 2^k + 2 \\ &\Rightarrow 2(k + 1) + 1 < 2^k + 2 \end{align*}

Now we need to show that $2^k + 2 < 2^{k + 1}$.

$2^k < 2^{k + 1}\Rightarrow 2^k + 2 < 2^{k + 1} + 2$

This is where I'm stuck. Any help on how to proceed is much appreciated.

Answer 1

Continuing from your step $2(k+1)+1<2^{k}+2$.

Since $k\geq 3$, then $2<2^{k}$.

So, $2(k+1)+1<2^{k}+2<2^{k}+2^{k}=2^{k+1}$

$\therefore 2(k+1)+1<2^{k+1}$.

Answer 2

You're doing fine up until near end. Note that for $k \ge 3$, (actually, for any $k \gt 1$), you have $2 \lt 2^k$, so

$$2^k + 2 \lt 2^k + 2^k = 2^{k + 1} \tag{1}\label{eq1A}$$

with which you can then finish your inductive proof.

Answer 3

$2^{k} + 2 < 2^{k + 1}$

$2^{k} + 2< 2\cdot 2^{k}$

$2< 2^{k}$

This is trivially true for $k = 3$, and $2^{k}$ is an increasing function, so the inequality is true and the induction is complete. $\blacksquare$