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?
$\endgroup$ 23 Answers
$\begingroup$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}$$
$\endgroup$ $\begingroup$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.
$\endgroup$ $\begingroup$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$
