Prove by induction on $n\geq k$ that $n^3 \lt 3^n$. What is the value $k$?
It looks like $k$ should be $0$ after trying random values but obviously that is a terrible way of doing things.
Proof:
P(n): n^3<3^n
Assume k holds
Prove k+1
P(k+1): (k+1)^3<3^(k+1)
At this point, I am not entirely sure where to go. Any advice would be great.
Thanks,
To proove what orion suggests you should prove, define the function $f(x):= \frac{(x+1)^3}{3}$ and the function $g(x):= x^3$. We need to prove that $f(x)<g(x)$ for all $x \geq k$, for some natural number $k$.
But $f(3) = \frac{64}{3} < 27 = g(3)$. And so it sufficies to show that for all $x \geq 3$ $f'(x) \leq g'(x)$.
If you calculuate $f'$ and $g'$ and rearrange this inequality it boils down to showing that
$$(2x+1)(x-1) \geq 0 \quad \forall x \geq 3,$$
which is true.
EDIT If you don't know calculus, let's show directly that $\frac{(x+1)^3}{3} < n^3$ for all $n \geq 3$.
Multiply both sides by $3$, expand the brackets on the LHS, rearrange and get the equivalent statement:
$$2n^3 - 3n^2 -3n-1 > 0 .$$
But
$$2n^3 - 3n^2 -3n-1 > 2n^3 - 3n^2 -3n = n(2n^2 - 3n -3)$$
so it suffices to show that
$$n(2n^2 - 3n -3)>0.$$
Divide both sides by the positive number $n$, and see that we just need to show
$$2n^2 - 3n -3>0$$
for all $n \geq 3$.
Work out the roots of the quadratic using the formula to get that this is equivalent to
$$(n - \frac{3- \sqrt{31}}{4})(n - \frac{3+ \sqrt{31}}{4}) > 0.$$
Now it suffices to show that
$$\frac{3+ \sqrt{31}}{4} < 3,$$
but this rearranges to $$31 < 81$$
which is true.
First we compute a little, systematically. We have
$0^3\lt 3^0$;
$1^3 \lt 3^1$;
$2^3\lt 3^2$;
$3^3=3^3$, so there inequality $n^3\lt 3^n$ is not true at $n=3$;
$4^3=64$, $3^4=81$, so $4^3\lt 3^4$;
$5^3=125$, and $3^5=243$;
$6^3=216$, and $3^6=729$;
$7^3-343$, and $3^7=2187$.
If this were a horse race, it looks as if the horse $3^n$ is now well ahead of the horse $n^3$, and is getting further and further ahead as time goes on.
We will prove that $n^3\lt 3^n$ if $n\ge 4$.
The result is certainly true at $n=4$. We show that for any $k\ge 4$, if $k^3\lt 3^k$, then $(k+1)^3\lt 3^{k+1}$. There are several ways to do this. We mention a couple.
(i) We have $3^{k+1}=3\cdot 3^k$. By the induction assumption, $3^k\gt k^3$. So it is enough to show that $3k^3\ge (k+1)^3$, or equivalently that $3\ge \left(1+\frac{1}{k}\right)^3$. Note that $\left(1+\frac{1}{4}\right)^3\lt 3$, and if $k\gt 4$, then $\left(1+\frac{1}{k}\right)^3\lt \left(1+\frac{1}{4}\right)^3$. This completes the proof. The idea behind this proof is that if we increment $n$ by $1$, then $3^n$ jumps by a factor of $3$, but $n^3$ only jumps by a factor of $\left(\frac{n+1}{n}\right)^3$, which very soon is $\lt 3$.
(ii) We want to show that if $k\ge 4$, then $3k^3\ge (k+1)^3$, or, expanding, that $2k^3\gt 3k^2+3k+1$. Note that if $k\ge 4$, then $2k^3\ge 8k^2$. But $3k^2+3k+1\lt 3k^2+3k^2+k^2=7k^2$.
Alternately, we could look at the function $2x^3-3x^2-3x-1$, and use techniques from the calculus or elsewhere to find out when it is positive.
