Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

3 Answers 3

up vote 4 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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