2
$\begingroup$

I've no clue how to go ahead with this, all I know is it will be solved with induction.

  1. Proved it's true for $k=10$
  2. Assumed it's true for $k$
  3. Need to prove that $2^{k+1} > ({k+1})^3$

Any pointers? I'm struggling with tough Induction questions so if you have any general tips to solve such questions it'll be great.

3 Answers 3

4

If you know $2^k > (k)^3$ and want to prove $2^{k+1} > ({k+1})^3$ the obvious thing to do is multiply the first by two so that you have $2^{k+1} > 2 k^3$ now if we could show that $2k^3 \ge (k+1)^3$ we could put these two inequalities together to complete the proof.

By expanding out and collecting like terms we have to prove $k^3 \ge 3k^2 + 3k + 1$ but that's an easy consequence of $k^3 \ge 3k^2 + 3k^2 + k^2$ which holds because $k \ge 10$ (dividing both sides by $k^2$).

4

When you pass from $2^k$ to $2^{k+1}$, the number doubles. If you could show that passing from $k^3$ to $(k+1)^3$ increases the number by a factor less than $2$, you’d be in business. How big is $\frac{(k+1)^3}{k^3}$? If $k\ge 10$, then

$\frac{(k+1)^3}{k^3}=\left(\frac{k+1}k\right)^3=\left(1+\frac1k\right)^3\le\left(1+\frac1{10}\right)^3=\left(\frac{11}{10}\right)^3=\frac{1331}{1000}<2\;.\tag{1}$

Thus, if $2^k>k^3$ and $k\ge 10$, we have

$2^{k+1}=2\cdot 2^k>\frac{(k+1)^3}{k^3}\cdot 2^k>\frac{(k+1)^3}{k^3}\cdot k^3=(k+1)^3\;,$

exactly as desired.

Writing it out in one go like that may make it look more mysterious than it really is. All I really did was ask myself what happens to the two sides of the inequality $2^k>k^3$ when $k$ is replaced by $k+1$. Clearly the lefthand side is doubled. What happens to the righthand side (in terms of multiplicative increase) isn’t so obvious, but at least we can say that it gets multiplied by $\frac{(k+1)^3}{k^3}$:

$\begin{array}{c} &2^k&>&k^3\\ \text{multiply by }2&\downarrow&&\downarrow&\text{multiply by }\frac{(k+1)^3}{k^3}\\ &2^{k+1}&\overset{?}>&(k+1)^3 \end{array}$

Clearly the inequality in the bottom row will be true if $2\ge\frac{(k+1)^3}{k^3}$, so we just have to make sure that this is the case $-$ which is exactly what I did with the calculation $(1)$.

0

You have: $(k+1)^3 \stackrel{k\ge 10}{\lt} 2\cdot k^3 \stackrel{hyp.}{\lt} 2\cdot 2^k$