# Prove $2^n > n^3$ [duplicate]

Let $P(n)$ be the property: $2^n > n^3$. Let's use mathematical induction to prove that $P(n)$ is true for $n\geq10$.

Basis: $P(10): 2^{10} > 10^3 \Leftrightarrow 1024 > 1000$ which is true.

Hypothesis: $P(k): 2^k > k^3$

Inductive step: we have to prove $P(k) \Rightarrow P(k+1)$:

$2^{k+1} = 2\cdot 2^k > 2\cdot k^3 = k^3 + k^3$

Everything is clear up to here, but then it goes on like this:

$k^3 + k^3 \geq k^3 + 7\cdot k^2$

Question here: How to prove that $k^3 > 7\cdot k^2$ ? I know it's because $n\geq 10$, but how to prove it? Besides empirically - which shows it's true.

Then the proof goes on:

$k^3 + k^3 \geq k^3 + 3\cdot k^2 + 3\cdot k + 1$

Question here: I suppose it's the same "technique" like above, isn't it? If not, how to prove that:

$k^3 \geq 3\cdot k^2 + 3\cdot k + 1$ ?

-

## marked as duplicate by Martin Sleziak, iostream007, azimut, O.L., mauAug 2 '13 at 7:45

For your second question, you should not try to prove that $k^3 \geq 3k^2 + 3k + 1$. Instead, use the earlier result that $k^3 + k^3 \geq k^3 + 7k^2$, and then show that $7k^2 \geq 3k^2 + 3k + 1$. Then it trivially follows that $7k^2 = 3k^2 + 3k^2 + 1k^2 \geq 3k^2 + 3k + 1$ for $k \geq 1$. –  TMM Oct 7 '11 at 18:25

In the induction step you're allowed to assume $k\ge 10$ because $k=10$ was proved in the base case. This directly implies $k>7$, and because $k^2$ is positive you can multiply on both sides to get $k^2>7k^2$.
If you want to be completely formal about it, you could insist that mathematical induction must always start at $0$. In that case, the property you actually prove by induction is $2^{m+10}>(m+10)^3$ for all $m\ge 0$, and in your induction step $k$ would be an abbreviation for $j+10$ for some $j\ge 0$. Then $j\ge 0$ implies $j+10\ge 10$ which is the same as $k\ge 10$.
I don't really understand why they've picked up 7 when (as you said) saying $k>7$. Why not 6 or 8? –  Flavius Oct 7 '11 at 18:31
In general, not except for "try something that feels like it ought to work, and if it doesn't, try something else". If it turns out to be difficult to guess a good value, you could use a unknown instead of the magic number $7$, collect conditions it needs to satisfy as you go, and then afterwards look for a choice that satisfies all of them. In practice, though, this often tends to add confusion and complexity instead of reducing it -- partly because an extra unknown makes it harder to predict what will work and what won't. So I wouldn't recommend that tactic as the first option. –  Henning Makholm Oct 7 '11 at 20:41
I kind of "feel" why 7 is a good choice, I just have to go backwards from what I need and see from there how many k I need. $3k^2+3k+1$ "correlates" to 7 k. Thanks. Accepted –  Flavius Oct 7 '11 at 20:56