Proof that $n^3 \leq 2^n$ for $n \geq 10$ by induction

Question

I'm trying to prove this statement and it got a bit clumsy but at least it seems to make sense. I'd like to know if this proof is valid. Here's what I managed to do:

First the base case:

$n = 10$ $$n^3 \leq 2^n$$ $$1000 \leq 1024$$

I assumed that it's true for $k$: $$k^3 \leq 2^k$$

Then I tried to prove that it's true for $k+1$. First I multiplied both sides by $2$:

$$2k^3 \leq 2^k \cdot 2$$ $$2k^3 \leq 2^{k+1}$$ $$2k^3 \leq 2^k + 2^k$$ $$k^3 + k^3 \leq 2^k + 2^k$$

Since $n \geq 10$:

$$(k+1)^3 \leq k^3 + k^3 \leq 2^k + 2^k$$

therefore $$(k+1)^3 \leq 2^{k+1}$$

Can someone confirm this, please?

Answer 1

I would say that this proof has the right idea in the broad picture - it clearly follows the form of an inductive proof, for instance - but it has some notable issues; the biggest problem is that you do all sorts of tiny manipulations to the expression $$k^3 \leq 2^k$$ to get to $$k^3 + k^3 \leq 2^k+2^k$$ but it's really not clear why. It would be clearer to just say that you're multiplying everything by $2$ to get $$2k^3 \leq 2^{k+1}.$$ And then to claim (with some proof) that $(k+1)^3 \leq 2k^3$. As it is, you have introduced a really fine (and probably unnecessary) level of detail for some series of symbolic manipulations that don't accomplish much, but then leave the most important step unjustified!

In particular, you need to argue that $(k+1)^3 \leq 2k^3$ somewhere - you can do this by noting that $$\frac{(k+1)^3}{k^3}=\left(1+\frac{1}k\right)^3\leq \left(1+\frac{1}{10}\right)^3 \leq 2$$ and then rearranging. You can also expand $$(k+1)^3 = k^3 + 3k^2 + 3k + 1 = \left(1+\frac{3}k+\frac{3}{k^2}+\frac{1}{k^3}\right)k^3 \leq \left(1+\frac{7}k\right)k^3 \leq \left(1+\frac{7}{10}\right)k^3$$ to get the same result - or even write out an inductive proof of the fact, if you really want to avoid rational arithmetic.

The other, smaller, issue is that you seem to be using $n$ at some places (for bounds) and $k$ at other places, when you really mean to refer to the same variable.

Answer 2

Your solution is perfectly valid. The only step I see that could be improved is $$(k+1)^3\leq k^3+k^3.$$ Fortunately, this is very easy to justify: $$\frac{(k+1)^3}{k^3}=\left(1+\frac1k\right)^3\leq\left(1+\frac1{10}\right)^3=\frac{1331}{1000}<2.$$

Answer 3

Your solution looks good, but you might want to add more details as to why

$$(k+1)^3\leq k^3+k^3$$

This can be seen explicitly as

$$(k+1)^3=1 + 3 k + 3 k^2 + k^3=k^3+k^3\left(\frac{3}{k}+\frac{3}{k^2}+\frac{1}{k^3}\right)$$

Since $k\geq 4$ we have

$$k^3+k^3\left(\frac{3}{k}+\frac{3}{k^2}+\frac{1}{k^3}\right)\leq k^3+k^3\left(\frac{3}{4}+\frac{3}{4^2}+\frac{1}{4^3}\right)=k^3+\frac{61}{64}k^3<k^3+k^3$$

Answer 4

Just to give one more proof of the crucial missing argument,

$$(k+1)^3=k^3+3k^2+3k+1\le k^3+3k^2+3k^2+k^2=k^3+7k^2\le k^3+k^3$$

The first inequality is satisfied for all $k\ge1$, and the second for all $k\ge7$.