Prove $\forall n \geq 10, 2^n > n^3$

Question

Prove $\forall n \geq 10, 2^n > n^3$

base case: $n = 10$

$2^{10} = 1024$

$10^3 = 1000$

$1024 > 1024$.

So $P(k)$ holds for $k = n$. We seek to show $P(k+1)$ holds:

---

We know $2^k > k^3$.

$2^k+3k^2+3k+1>k^3+3k^2+3k+1 = (k+1)^3$

$\iff 2^k+3k^2+3k+1>(k+1)^3$

Let us compare $k^3$ and $3k^2+3k+1$:

$k^3$ $\Box$ $3k^2+3k+1$

$k^3-3k^2-3k$ $\Box$ $1$

$k(k^2-3k-3)$ $\Box$ $1$.

$k^2-3k-3 > 0$, $\forall k \geq 10$,

$\implies k^3 > 3k^2+3k+1, \forall k \geq 10$.

Therefore $2^k + k^3 > 2^k + (3k^2+3k+1)$.

We know $2^k > k^3$,

so $2^{k+1} = 2^k+2^k > 2^k + k^3 > 2^k+3k^2+3k+1 > (k+1)^3$

$\implies 2^{k+1} > (k+1)^3$.

Therefore $P(k+1)$ holds and our hypothesis is proven.

---

I don't really know how else to segue into the argument about comparing $k^3$ to $3k^2+3k+1$, is this ok notation?

Answer 1

Your proof is valid. You segue is clunky but acceptable. It's a matter of personal style but I'd do the following.

Induction step: Assume for some $k$ that $2^k > k^3$.

If we could show that $k^3 > 3k^2 + 3k + 1$ we'd have:

$2^{k+1} = 2^k + 2^k > k^3 + k^3 > k^3 + 3k^2 + 3k + 1 = (k+1)^3$

and we'd be done.

So it suffices to prove $k^3 > 3k^2 + 3k + 1$ for $k \ge 10$.

So.....

But it's a matter of style.

====

I'd also prove $k^3 > 3k^2 + 3k + 1$ via

$k^3 > 10k^2 = 3k^2 + 7k^2 > 3k^2 + 70k = 3k^2 + 3k + 67k > 3k^2 + 3k + 1$.

but your way works too.

Or... maybe I'd do it:

As $k > 0$ I can conclude $k^3 > 3k^2 + 3k + 1$ when $k > 3 + 3/k + 1/k^2$. As $k > 3$ $3/k + 1/k^2 < 3/k + 1/k = 4/k \le 1$ if $k \ge 4$ so $k^3 > 3k^2 + 3k +1$ for all $k \ge 4$.

Answer 2

I see your logic: you prove the chain $$ 2^{k+1}=2^k+2^k>k^3+k^3>k^3+3k^2+3k+1=(k+1)^3 $$ where the first inequality is due to the induction hypothesis and the second is because of the inequality $k^3>3k^2+3k+1$ ($k\geq 10$) for which you supply a separate proof. I think this is a good approach although you can write it more succinctly and clearly. You also can shorten the proof for $k^3>3k^2+3k+1$ as follows $$ k\geq 10\implies k^3\geq10k^2>3k^2+3k^2+k^2>3k^2+3k+1. $$ Alternatively, observe that $$ 2k^3>(k+1)^3\iff2>\left(1+\frac{1}{k}\right)^3\iff k>\frac{1}{\sqrt[3]{2}-1}\approx 3.84732 $$ so, of course, if $k\geq 10$ then you also have $2k^3>(k+1)^3$.