Show by induction that $n^3 \leq 3^n$ for all natural numbers n.

I need to show, using induction, that $n^3\leq 3^n$ for all natural numbers $n$.

I tried the three steps to prove by induction

putting $n=1$ then $n=k$ and at last I need the idea when I substitute $n=k+1$ to prove this also satisfies when $n=k$ is true.

-

To prove the statement $P_n$ by induction for all natural $n$, you need to show that

• $P_1$ is true
• if $P_k$ is true, then $P_{k+1}$ is true as well.

For the first part, $P_1$ states that $1^3 \leq 3^1$. Is that true?

Now for the second part, assume $P_k$ is true, i.e. we assume that $k^3 \leq 3^k$, and would like to prove that $(k+1)^3 \leq 3^{k+1}$. Can you complete the proof?

-
yes thanks for a neat and clear answer – sbrajagopal26 Jul 2 '13 at 14:15

You want to show that if $n^3 \le 3^n$ for some $n$, then $(n+1)^3 \le 3^{n+1}$.

The obvious way to do this is to show that $(n+1)^3 \le 3n^3$, because then you have $(n+1)^3 \le 3n^3 \le 3\times3^n = 3^{n+1}.$ Unfortunately it is not true that $(n+1)^3 \le 3n^3$ in general; but you should be able to show, by expanding $(n+1)^3$, that it is true whenever $n \ge 3$.

And now you can check by hand that $n^3 \le 3^n$ when $n \le 3$; and deduce the general case by induction for $n > 3$.

-

Observe that $3^0>0^3,3^1>1^3$ and $3^2>2^3$

So, the proposition is true for $P(0),P(1),P(2)$

Let $P(m)$ is true i.e., $3^m\ge m^3$

For $P(m+1),$

$3^{m+1}=3\cdot 3^m\ge3m^3$ which needs to be $\ge (m+1)^3$

$\implies 3\ge \left(1+\frac1m\right)^3$

Now, $\left(1+\frac12\right)^3=\frac{27}8>3,\left(1+\frac13\right)^3=\frac{64}{27}<3$

and $\left(1+\frac1m\right)^3>\left(1+\frac1{m+1}\right)^3$ for $m\in N^+$

$\implies \left(1+\frac1m\right)^3<3$ for $m\ge 3$

So, the proposition is true for $P(m)$ for $m\ge 3$ and we have already proved for $m=1,2$

-
thank you ..appreciate it – sbrajagopal26 Jul 2 '13 at 14:15
@sbrajagopal26, my pleasure. Hope I could make the idea clear – lab bhattacharjee Jul 2 '13 at 14:16
@TonyK, why have you deleted your comment? – lab bhattacharjee Jul 2 '13 at 14:23
@lab, because I wanted to edit it after the time limit expired. But while I was editing it, you changed your answer to address my concerns. – TonyK Jul 2 '13 at 18:43