1
$\begingroup$

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

  • 1
    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$.2011-10-07

1 Answers 1

5

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

  • 0
    Irrelevant to the question, but there is a more natural approach. We have $\frac{2^{n+1}}{2^n}=2$. Now look at $\frac{(n+1)^3}{n^3}=(1+1/n)^3$. Already if $n \ge 4$ this is less than $2$. So if $n \ge 4$, and we increment $n$ by $1$, the exponential grows by a factor of $2$, and the cube grows by a factor <2. So if $k \ge 4$, and 2^k>k^3, we will have 2^n >n^3 for all $n\ge k$. And at $k=10$, 2^k>k^3.2011-10-08