$n^3+n<3^n$ for $n \geq4$ by induction.

Solution 1:

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.

Solution 2:

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.