$n^3+n<3^n$ for $n \geq4$ by induction. To prove that $n^3+n<3^n$ for $n \geq4$ by induction.
I have proved the fact but it became very long and I have to use two more induction proof within the proof. 
Can someone give a better solution by induction?
Thank You.


 A: From what you did, it suffices to show that $3k^2+3k+2\le 2\cdot 3^k$ for $k\ge 4$. It seems messy to compare the polynomial and the exponential directly, so instead let's see if we can show that $3k^2+3k+2\le 2\cdot(k^3+k)$, which will do the job.
For this, note that $3\le(k-1)$, since $k\ge4$, so $3k^2+3k+2\le (k^3-k^2)+(k^2-k)+2$, and you are done, with room to spare.
A: As indicated by @Andrés, it suffices to prove that 
$$
3k^2 +3k + 2 < 2(k^3 + k),
$$
which is
$$
2k^3 - 3k^2 - k -2 >0.
$$
Rewrite this as
$$
(k-1)(2k^2-k-2)-4 >0.
$$
By studying the quadratic, when $k \geqslant 4$,  we have 
$$
\mathrm{RHS}\geqslant 3\times (2\times 16 -4-2) -4= 3\times 26 -4 >0,
$$
hence the induction step. 
This might not be the easiest way, but it is the direct one, I think. 
A: Inductive step:
Assume $n^3+n\lt3^n$.
$(n+1)^3+(n+1)=n^3+3n^2+3n+1+n+1=(n^3+n)+3n^2+2n+2\lt3^n+3n^2+3n+2=3^n(1+3^{1-n}n^2+3^{-n}\cdot2)\lt3^n(1+\frac{n^2}{3^{n-1}}+1)\lt3^n(3)=3^{n+1}$, because $n^2\lt3^{n-1}$ for $n\ge4$. 
(The last inequality is easy to prove.)
A: $n^3 + n < 3^n \tag 1$
certainly holds for $n = 4$; so this will be the base case; assuming (1) binds for some $n$, then
$3(n^3 + n) < 3^{n + 1}; \tag 2$
now,
$(n + 1)^3 + (n + 1) = n^3 + 3n^2 + 3n + 1 + n + 1 = n^3 + 3n^2 + 4n + 2, \tag 3$
and
$3(n^3 + n) = 3n^3 + 3n, \tag 4$
so what we need is
$n^3 + 3n^2 + 4n + 2 \le 3n^3 + 3n, \; n \ge 4; \tag 5$
this is true if
$3n^3 + 3n - n^3 - 3n^2 - 4n - 2 = 2n^3 - 3n^2 -n - 2 \ge 0, \; n \ge 4; \tag 6$
now, as our colleague xbh has observed,
$2n^3 - 3n^2 - n - 2 = (n - 1)(2n^2 - n - 2) - 4; \tag 7$
we have
$n \ge 4 \Longrightarrow n - 1 \ge 3; \tag 8$
also we have
$n \ge 4 \Longrightarrow 2n^2 - n - 2 = n^2 +  n(n - 1) - 2 \ge  16 + 4 \cdot 3 - 2 = 26; \tag 9$
thus,
$n \ge 4 \Longrightarrow 2n^3 - 3n^2 - n - 2 \ge 3 \cdot 26 - 4 = 74; \tag{10}$
we see that (6) binds, thus does (5), hence the induction is complete and (1) holds for all $n \ge 4$.
