Proving $2n+1 < 2^{n}$ using mathematical induction. I'm learning about how use mathematical induction.
I'm tasked with proving the inequality shown in (1). It is a requirement that I use mathematical induction for the proof.
$(1) \quad P(n):\quad 2n+1 < 2^{n}, \quad n \ge 3$
I would like some feedback regarding whether my proof is valid and if my use of the induction hypothesis is correct. My proof:
Prove base case:
$(2) \quad P(b):\quad 2\cdot3+1 < 2^{3}, \quad b=1$
$(3) \quad P(b):\quad 7<8$
Assume that $P(n)$ is true for an arbitrary $k$, with $n \ge k \ge 3$. (This is the induction hypothesis, IH)
$(4) \quad P(k):\quad 2k+1 < 2^{k}$
The inductive step:
$(5) \quad P(k+1):\quad 2(k+1)+1 < 2^{k+1}$
$(6) \quad 2k+3 < 2^{k}\cdot 2$
Using the IH we get (7). I just added 2 to both sides of the inequality so that the LHS in (6) and the IH is equal.
$(7) \quad 2k+3 \overset {IH}{<} 2^{k}+2$
Subtracting 2 from both sides yields us $P(k)$:
$(8) \quad 2k+1 < 2^{k}$
Which concludes the proof that $P(n)$ is true for every $n \ge 3$
Is my proof valid? Is my use of the IH correct?
I am aware that a similar problem is asked here.
 A: It's not clear to me how you proved that $P(k) \implies P(k + 1)$. You have a collection of inequalities $(5), (6), (7), (8)$, but I don't see which of them are implied by the others. Here's an alternative approach.
Assume that $P(k)$ is true for some $k$, where $k \geq 3$. It remains to show that $P(k + 1)$ is true. Indeed, observe that:
\begin{align*}
2(k + 1) + 1 
&= 2k + 3 \\
&= (2k + 1) + 2 \\
&< 2^k + 2 &\text{by the induction hypothesis} \\
&< 2^k + 8 \\
&= 2^k + 2^3 \\
&\leq 2^k + 2^k &\text{since $3 \leq k$, and $2^x$ is an increasing function} \\
&= 2 \cdot 2^k \\
&= 2^{k + 1}
\end{align*}
as desired.
A: You know it for $n=3$. Suppose this is true for $n$, i.e., $2n+1<2^n$. Let us prove it for $n+1$, i.e., $2(n+1)+1<2^{n+1}$. You have
$$
2n+3=(2n+1)+2<2^n+2 \le 2^{n+1}.
$$
The last inequality is true because $n\ge 3$.
A: Base case:
$n=3 \implies 7<8$ ok
Inductive step:
let's assume: $2n+1 < 2^{n}$
we want to prove that: $2n+3 < 2^{n+1}$
$$2n+3=2n+1+2\overset {IH}{<} 2^n+2=2(2^{n-1}+1)\overset {?}{<} 2\cdot2^n=2^{n+1}$$
we can easily check that
$$2^{n-1}+1< 2^n\iff2^n-2^{n-1}>1\iff2^{n-1}(2-1)>1 \quad \forall n>1$$
thus
$$2n+3<2^{n+1} \quad \square$$
A: I want to suggest an alternative way just to be more systematic:
Let $a(n) = 2n+1$ and $b(n)= 2^n$ where $n \ge 3$. Then for $n=3$, we have $7 = a(3) < b(3) = 8$. Then assume inductively that $a(n) < b(n)$ and $n > 4$. Then, for $n+1$, we have $$a(n+1) = 2n+3 = 2n+1+2 = a(n)+2 < b(n)+2$$ 
by inductive hyphotesis. But notice that $$b(n)+2 = 2^n+2 < 2 \cdot 2^n = 2^{n+1} = b(n+1)$$
Therefore, we have $$a(n+1) < b(n)+2 < b(n+1) \implies a(n+1) < b(n+1)$$
A: Hypothesis: 
1) You assume that $2n+1 < 2^n$ for an $n.$
Step:
Assuming the hypothesis : 
Show that $2(n+1) +1 < 2^{n+1}$, I.e.
the formula holds for $n+1.$
$2n+1 + 2 =$
$2(n+1) +1 < 2^n +2 ;$
$2$ has been added to both sides of $2n+1 <2^n$ (hypothesis) .
LHS : $2(n+1) +1$.
RHS: $2^n +2 \lt 2^n +2^n= $
$2(2^n) =2^{n+1}$.
since $2 \lt 2^n$ for $n \ge 3.$
Hence:
$2(n+1)+1 < 2^{n+1}.$
A: Alternatively, without induction: for $n\ge 3$:
$$2^n=(1+1)^n=1+n+\cdots +n+1>2n+1.$$
