Use the PMI to prove the following for all natural numbers $3^n≥1+2^n$

Question

Use the PMI to prove the following for all natural numbers

$3^n≥1+2^n$

Base Case: $n=1$

$3^1≥1+2^1$

$3 ≥ 3$, which is true

Inductive Case:

Assume $3^k ≥ 1+2^k$

[Need to Show for k+1]

$3^{(k+1)} \ge 1+2^{(k+1)}$

Now from here i always get stuck trying to show this next step. I already saw that this same question is asked on this website but i still don't understand why the steps are correct.

for example,

$3^{(k+1)}=3^k⋅3 \ge (1+2^k)3$

how does the RHS turn into that? is there an algebra step that i just dont remember learning?

Answer 1

Assume $$3^k\ge 1+2^k$$ Add $2^k$ to both sides: $$3^k+2^k\ge 1+2^k+2^k=1+2^{k+1}$$ Now notice that $3^{k+1}=3\cdot 3^k=3^k+2\cdot 3^k\ge 3^k+2^k$ So, we combine $3^k+2^k\ge 1+2^{k+1}$ with $3^{k+1}\ge 3^k+2^k$ and get $$3^{k+1}\ge 1+2^{k+1}$$

Answer 2

$3^{(k+1)}=3^k⋅3 \ge (1+2^k)3 \ge (\frac{1}{3}+2^k\cdot\frac{2}{3})3=(1 + 2^{k+1})$

Hope this helps.

Answer 3

$$3^{k+1}\geq (1+2^k)\cdot 3 = 3+3\cdot 2^k > 1+2\cdot 2^k=1+2^{k+1}$$

The first step you already got, the second step is the distributive law, the third step is because $3>1$ and $3\cdot 2^k>2\cdot 2^k$.