Proof by Induction for Exponential Term

Question

Prove by mathematical induction that $3^n\geq n2^n \text{ } \forall n\in \mathbb{N}$ the set of natural numbers. So after showing that $S(1)$ is true, we assume $S(k)$ is true and try to prove that $S(k+1)$ is true. I make it this far, and get stuck with further justification:

$$\begin{align} 3^k &\geq k2^k \\ 3\times 3^k &\geq 2\times k2^k \text{ since } 3>2 \\ 3^{k+1} & \geq k2^{k+1} \end{align}$$

But now I have to somehow get that $k+1$ term in front of $2^{k+1}$, but I'm not sure how to do it in a way that's justified. Perhaps I've taken a wrong starting approach. How would you do this?

Answer 1

Assume that $3^k \ge k\cdot 2^k$ for some $k$. So

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

for $k\ge 2$, you have $3\cdot k = 2\cdot k+k \ge 2\cdot k+2 = 2(k+1)$, so

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

but, initially, you must show that S(1) and S(2) is true, because the induction step holds only for $k\ge2$.

Answer 2

At your second line, you are throwing away information. Instead how about $3^{k+1}\ge 3k2^k=k2^{k+1}+k2^k$? If you can show that $k2^k\ge 2^{k+1}$ then you deduce $3^{k+1}\ge k2^{k+1}+2^{k+1}=(k+1)2^{k+1}$.

Answer 3

The inequality is true for $n=2,3 $ We have that: $$3^n \ge n2^n$$ $$3^{n+1}\ge 3n2^n$$ $$3^{n+1}\ge n2^{n+1}+n2^n$$ It's easy to show that for $n\ge 2$ $$n2^n \ge 2^{n+1}$$ $$n \ge 2$$ Therefore $$3^{n+1}\ge (n+1)2^{n+1}$$

---

Another way ... $$3^n \ge n2^n \implies \left (\frac 32 \right )^n \ge n \implies \left (\frac 32 \right )^{n+1} \ge \frac {3n} 2$$ $$\left (\frac 32 \right )^{n+1} \ge n+ \frac {n} 2$$ it's easy to show that $$n+ \frac {n} 2 \ge n+1$$ $$ \frac {n} 2 \ge 1$$ $$ {n} \ge 2$$ So it's true for $n \ge 2$ and: $$\boxed {\left (\frac 32 \right )^{n+1} \ge n+1}$$