Proving Inequalities With Mathematical Induction

Question

I'm currently working on this problem:

$$ 1 + 2^n + ≤ 3^n \text{ for all } ≥ 1 $$

So far, I have:

Basis Step: $ 1 + 2^1 ≤3^1 $ $ P(1) \text{ is true} $

Inductive Step: Assume P(k) holds, prove P(k+1)

$P(k) = 1 + 2^k ≤ 3k$

$ P(k+1) = 1 + 2^{k+1} ≤ 3^{k+1} \text{ (I.H.)}$

$ 1 + 2^{k+1} = 1 + 2 * 2^k$

$ \quad \quad \, \, \quad = 2 * 2^k + 1 ≤ 2 * 3^k$

But now, I'm unsure what to do next. Any help would be aprreciated! Thank you.

Answer 1

You are almost done. $$\quad \quad \, \, \quad 2 * 2^k + 1 ≤ 2 * 3^k<3*3^k=3^{k+1}$$

Answer 2

\begin{align*} 1+2^{k+1}&=1+2\cdot 2^{k}\\ &\leq 1+2\cdot(3^{k}-1)\\ &=2\cdot 3^{k}-1\\ &\leq 2\cdot 3^{k}\\ &\leq 3\cdot 3^{k}\\ &=3^{k+1}. \end{align*}

Answer 3

$$3^{k+1}\ge 3\cdot 2^k +3 > 2^{k+1}+1$$

Answer 4

First use induction to prove $2^{n} < 3^n$.
Then $1 + 2^n \leq 3^n$ immediately follows.

Answer 5

The inductive step: $$1+2^{n+1}=1+2\cdot 2^n=1+2^n+2^n\le 3^n+2^n\le 3^n+3^n+3^n=3\cdot 3^n=3^{n+1}.$$

Without induction: $$1+2^n\le 3^n=(1+2)^n=1+A+2^n, \ \ A\ge 0.$$

Answer 6

Another possible solution is to factor the difference of powers:

$$3^n-2^n = \underbrace{(3-2)}_{=1} \underbrace{\sum_{i=0}^{n-1} 2^i 3^{n-1-i}}_{\ge 1} \ge 1$$

Rearranging gives $1+2^n \le 3^n$.