Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question already has an answer here:

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

share|cite|improve this question

marked as duplicate by Martin Sleziak, iostream007, azimut, Start wearing purple, mau Aug 2 '13 at 7:45

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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
up vote 5 down vote accepted

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

(But nobody is that formal about it, except when they interact with computer proof systems).

share|cite|improve this answer
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
Perhaps 6 and/or 8 would work too. Try them! Since this is a proof, all that matters is that your choices work -- how you made them does not influence the validity of the proof. For that matter you could have rolled a die as long as the number that came up was one that made the proof work. – Henning Makholm Oct 7 '11 at 18:35
So there's no "rule of thumb" in such cases? – Flavius Oct 7 '11 at 20:30
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

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