Mathematical induction final step -- proving $n^3 \leq 2^n$, where $n\geq 10$

Question

I was solving an induction exercise, but I got stuck here, and I'd like a hint ($n \geq 10$).

Claim: $n^3 \leq 2^n$

I have that $3n^2 + 3n \leq 2^n - 1$, but I am unsure as to how to proceed.

Answer 1

It sounds like your question is specifically how to prove:

$n^3\leq 2^n$ holds for $n\geq 10$

Proof: For $n=10$, you have $n^3=10^3=1000<1024=2^{10}=2^n$.

Suppose for our induction hypothesis that it is true that $n^3\leq 2^n$ for some $n\geq 10$. We want to show that it follows for $n+1$ as well.

$$(n+1)^3=n^3+3n^2+3n+1 \leq^{I.H.} 2^n + 3n^2+3n+1\\ \leq 2^n + 3n^2+3n^2+6n^2\leq 2^n+10n^2\leq 2^n+n^3\leq^{I.H.}2^n+2^n=2^{n+1}$$

I made the jump from the end of the top line to the beginning of the bottom line by simply noting that for $n\geq 1$ that I am adding extra and multiplying by extra positive numbers greater than 1, thereby increasing the total. Also, noting that $n\geq 10$ tells me that $10n^2\leq n^3$.

Therefore $(n^3\leq 2^n)\wedge (n\geq 10)\Rightarrow (n+1)^3\leq 2^{n+1}$, so the claim is true for all $n\geq 10$.

Answer 2

Note: The following proves the inequality $3n^2 + 3n \leq 2^n - 1$ for $n\geq 10$. This appeared to be a possible interpretation of the OP's original question. Regardless, both inequalities are now addressed.

Here's the meat of the argument: \begin{align} 2^{k+1}-1 &= 2\cdot 2^{k}-1\tag{definition}\\[0.5em] &= 2(2^k-1)+1\tag{manipulate}\\[0.5em] &\geq 2(3k^2+3k)+1\tag{induction hypothesis}\\[0.5em] &= 6k^2+6k+1\tag{expand}\\[0.5em] &\geq 3k^2+9k+6\tag{since $k\geq 10$}\\[0.5em] &=3(k+1)^2+3(k+1).\tag{desired expression} \end{align}