I have already started the problem but I am unsure on how to proceed.
Prove $2n+3 \le 2^n$ for all integers $n \ge 4$.
Base Case:
- Choose $n = 4$.
- $2n + 3 \le 2^n$
- $2(4) + 3 \le 2^4$
- $8 + 3 \le 16$
- $11 < 16$
- $n = 4$ is true.
Inductive Step: Assume that $2k + 3 \le 2^k$ where $k \ge 4$. We show that $2(k+1) + 3 \le 2^{(k+1)}$.
How do I show that is true?
You know that $2k +3 \leq 2^k$. Add two to both sides: $2k + 3 + 2 \leq 2^k + 2$. Then you have that $2k + 3 + 2 = 2(k+1) + 3 \leq 2^k +2 < 2^{(k+1)}$. (Why is the last step true?)