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

Question

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.

---

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

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

Answer 3

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

Answer 4

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