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?

  • 3
    $\begingroup$ Hint: start with $3 \cdot 3^k \ge 3 \cdot k2^k\,$, instead, then prove $3 \cdot k2^k \ge (k+1) 2^{k+1} \iff 3 \ge 2\left(1+\frac{1}{k}\right)\,$. $\endgroup$ – dxiv Feb 10 '18 at 3:40

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$.


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}$.


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}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.