Prove that $2n+1 \leq 2^n$ for $n \geq 3$ using mathematical induction.

Question

Question: $2n+1 \leq 2^n$, for all $n \geq 3$

I've tried:

Basis: $P(3) = 7 \leq 8 $, so basis step is valid

Pick an arbitrary value from the universe, $k \geq 3$

Inductive Step: $2k + 1 \leq 2^k$

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

manipulation..., inequality proofs are troubling me so please correct the way I go about these.

$P(k+1) = 2k + 2 +1 \leq 2*2^k$

At this point, it is best to try to make the IH step look like the inductive step. $=(2k+1) + 2 \leq 2*2^k$

$=(2k+1) \leq 2*2^k -2$

Now, I know I'm supposed to find another inequality to use the transitive property of inequalities. However, at this step I'm completely lost. I can do the following:

$=2k+1 \leq 2(2^k -1)$ and now I'm stuck..., What did I do wrong and which techniques should I keep in mind when doing these sorts of proofs? Thanks.

Answer 1

You know something about $2k + 1$, and want to relate it to $2(k + 1) + 1$. The easiest way to do this here is to simply expand, so that you can use the induction hypothesis directly:

\begin{align*} 2(k + 1) + 1 &= \Big(2k + 1\Big) + 2 \\ &\le 2^k + 2 \\ &\vdots \\ &\le 2^{k + 1} \end{align*}

Now you need to fill in the vertical dots. One way to do this is to start with $2^{k + 1} = 2^k \cdot 2 = 2^k + 2^k$. Can you relate this to the line before the missing stuff?

Answer 2

For the inductive step notice that:

$2(n+1)+1=(2n+1)+2\le2^{n}+2\le 2^{n}+2^{n}=2\cdot 2^{n}=2^{n+1}$

Answer 3

Hint: Maybe it's nice to notice that $$2n+1 \leq 2^n \iff 2n \leq 2^n - 1 \iff 2n \leq 2^{n-1} + 2^{n-2} + \cdots 1$$before doing the induction.