Induction Help: prove $2n+1< 2^n$ for all $n$ greater than or equal to $3$.

Question

I understand that he expanded the left side but I'm having trouble figuring out what he did on the right side of the inequality. Where the did the $2$ (in circle) come from?

Answer 1

First, show that this is true for $n=3$:

$2\cdot3+1<2^3$

Second, assume that this is true for $n$:

$2n+1<2^n$

Third, prove that this is true for $n+1$:

$2(n+1)+1=$

$\color\red{2n+1}+2<$

$\color\red{2^n}+2=$

$2^n+\color\green{2^1}<$

$2^n+\color\green{2^n}=$

$2^{n+1}$

---

Please note that the assumption is used only in the part marked red.

Answer 2

In the induction hypothesis, it was assumed that $2k+1 < 2^k,\forall k \geq 3$, So when you have $2k + 1 +2$ you can just sub in the $2^k$ for $2k+1$ and make it an inequality. So that makes $$2k+1+2 < 2^k + 2$$ and since it was assumed $k\geq 3$ we also know that $2 < 2^k$. So now we have $$2k+1+2 < 2^k+2 < 2^k+2^k=2^{k+1}$$. Then by the transitive property we have $$2(k+1)+1 < 2^{k+1}$$

Answer 3

Most Important Step is
=> $2k+1+2 < 2^k$
=> $2k+1+2$
as $2k+1 = 2^k$
=> $2^k+2$
since $2<2^k$ so we can put $2^k$ inplace of 2
=> $2^k+2^k$
=> take common $2^k$
=> $2^k(1+1)$
=> $2^k.2$
=> $2^k+^1$
=> Hence $2(k+1)+1 < 2k+1$