# Proof by induction: inequality $n! > n^3$ for $n > 5$

I'm given a inequality as such: $n! > n^3$ Where n > 5,

I've done this so far:

BC: n = 6, 6! > 720 (Works)

IH: let n = k, we have that: $k! > k^3$

IS: try n = k+1, (I'm told to only work from one side)

So I have (k+1)!, but I'm not sure where to go from here.

I've been told that writing out: $(k+1)! > (k+1)^3$ is a fallacy, because I can't sub in k+1 into both sides, but rather prove from one side only.

Any Help on how to continue from here, would be much appreciated.

You have $(k+1)!=(k+1)k!>(k+1)k^3$ by the induction hypothesis. Now it suffices to show that if $k>5$ then $k^3 > (k+1)^2$. To do that, we write $(k+1)^2 = k^2 +2k+1 < k^2 + kk + k^2 = 3k^2 < kk^2 = k^3$, since we're assuming $k>5$.

Note that it is equivalent to prove that $n!/n^{3} > 1$ for all $n \geq 6$. You have proved for $n = 6$; suppose $n \geq 6$ is such that $n! > n^{3}$; then $$\frac{(n+1)!}{(n+1)^{3}} > \frac{n^{3}(n+1)}{(n+1)^{3}} = \frac{n^{3}}{(n+1)^{2}} = \frac{n^{3}}{n^{2}+2n+1} > \frac{n^{3}}{4n^{2}} = \frac{n}{4} > 1.$$ You know how to conclude.

Suppose $n \ge 6$ and $n! > n^3$. You want to show that this implies that $(n+1)! > (n+1)^3$.

Since $n! > n^3$ and $(n+1)! =(n+1)n!$, we have $(n+1)! > (n+1)n^3$.

So, we are done if we can show that $(n+1)n^3 \ge (n+1)^3$.

But, dividing by $n+1$, this is equivalent to $n^3 \ge (n+1)^2$. There are a variety of ways to prove this - you can even use induction.

Here is a direct way:

Since $n \ge 6$, $(n+1)^2 =n^2(1+\frac1{n})^2 \le n^2(1+\frac1{6})^2 \le n^2\frac{49}{36} < 2n^2$. But $n^3 \ge 6n^2 > 2n^2 > (n+1)^2$ and we are done.