A possible error in the inductive proof of $2k+1<2^k$ for $k\ge 3$

Question

This is the answer to a basic induction problem. I feel that that the author may have made a typo...

$2^k + 2^k = 2^k \cdot 2^1 = 2^{k+1}$

Answer 1

No, that is not a typo. What the author is saying is that since, by the assumption that $2k + 1 < 2^k$, one can substitute $2^k$ for $2k + 1$ in the equality $2k + 1 + 2 = 2(k + 1) + 1$ to find the inequality $2(k+1) + 1 < 2^k + 2$. Since $2^k + 2 < 2^k + 2^k = 2^{k+1}$, this inequality implies what you want to show.

Answer 2

Perhaps the following will make it easier for you to understand.

---

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

$2\cdot3+1<2^3$

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

$2k+1<2^k$

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

$2(k+1)+1=$

$2k+3=$

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

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

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

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

$2^{k+1}$

---

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