Proving an inequality using mathematical induction

Question

Using induciton, I have to prove following inequality: $$ 3^n > n2^n $$ I proved it for $n = 0$. Then assuming that the above is true, I try to prove it for $n+1$. So I start with: $$ (n+1)2^{n+1} = n2^{n+1} + 2^{n+1} = 2(n2^n+2^n)$$ Using the assumption: $$2(n2^n+2^n) < 2(3^n+2^n)$$ Now I have to reach the point where $2(3^n+2^n) < 3^{n+1}$ , but I have no idea how to get there.

Answer 1

1. Check the cases $n=0,1,2$ by computation.
2. Note that \begin{align*} & n(2^{n}+2^{n+1})\geq(n+1)2^{n+1}\\ \iff & n2^{n}\geq2^{n+1}\\ \iff & n\geq2. \end{align*}
3. Lastly, assume the inequality holds for some $n\geq2$. Then, by the above, $$ 3^{n+1}=3^{n}3>n2^{n}3=n2^{n}(1+2)=n2^{n}+n2^{n+1}=n(2^{n}+2^{n+1})\geq(n+1)2^{n+1} $$

Answer 2

The induction hypothesis is that $3^n>n\cdot 2^n$; then $$ 3^{n+1}=3\cdot 3^n>3n\cdot 2^n $$ Thus you want to see that $3n\cdot 2^n\ge (n+1)\cdot 2^{n+1}$, which is equivalent to $$ 3n\ge 2(n+1) $$ or $n\ge2$.

Well, this doesn't cover the cases $n=0$, $n=1$ and $n=2$, which you can prove directly: $3^0=1>0\cdot 2^0=0$; $3^1=3>1\cdot 2^1=2$; $3^2=9>2\cdot 2^2=8$.

Note that there is nothing wrong in doing like this, looking for what you need. Mathematical discovery is done this way.

Now you can go backwards and provide a “direct proof”.

The cases $0\le n\le 2$ are proved as before and the induction starts at $2$. Suppose $n\ge2$ and that $3^n>n\cdot 2^n$ holds.

Then $3n\ge 2(n+1)$, so $$ (n+1)2^{n+1}\le 3n\cdot 2^n<3\cdot 3^n=3^{n+1} $$

Answer 3

Try $2^n<3^n/n$ and factorise $3^n$: when you are at $$2(n2^n+2^n)<2(3^n+2^n)$$ you have $$2(n2^n+2^n)<2(3^n+2^n)<2(3^n+ \frac{3^n}{n})<3^n(2+\frac{2}{n})\,.$$ Since I have used very loose bounds $2+\frac{2}{n}\le 3$ for $n\ge 2$.