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?
Asked
Active
Viewed 2.3k times
0
-
By the induction hypothesis, $2k+1 < 2^k$ – ultrainstinct Feb 11 '16 at 05:53
-
1By induction hypothesis, $2k +1 < 2^k$, so $2k +1 + 2 < 2^k + 2$, which should clear up the circled "$+ 2$". By assumption, $k\ge 3$, so $2<2^k$. – BrianO Feb 11 '16 at 05:54
3 Answers
1
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}$$
ultrainstinct
- 2,651
0
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.
barak manos
- 43,109
0
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$
Abdul Malik
- 11
- 1