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.


enter image description here

  • Then what's your approach? Show it to us, and we might help you simplify it. – xbh Sep 8 at 1:09
  • @xbh I have posted my works – user8795 Sep 8 at 1:17
  • For a different approach, the inequality is quite loose, so you could "cheat" by breaking it into two, easier to prove, parts: $\,n^3 \lt 2 \cdot 3^{n-1}\,$ and $\,n \lt 3^{n-1}\,$ for $\,n \ge 5\,$. Adding the two together then gives the result. – dxiv Sep 8 at 1:42

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.

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.

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

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

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.