# Proving $n! > n^3$ for all $n > a$

Prove by induction: Find a, and prove the postulate by mathematical induction.

$$\text{For all}~ n > a,~ n! > n^3$$

Where ! refers to factorial.

So far I've done a bit of it, I'll skip right to the inductive statement and assume that $$k! > k^3$$, then try to prove $$(k+1)! > (k+1)^3$$

Inductive statement: $$(n+1)! > (n+1)^3$$

$$(n+1)^3= n^3 + 3n^2 + 3n + 1 < n! + 3n^2 + 3n + 1$$ (By Induction Hypothesis)

...But now I'm stuck. Does anyone know where to go next?

The induction hypothesis/statement lets you assume that $k!>k^3$ up to some $k$, not that $(k+1)!>(k+1)^3$ for said $k$. After you expand $(k+1)^3$ you are correct that $$k^3+3k^2+3k+1<k!+3k^2+3k+1$$ Now is where you should invoke the value of $a$. I'll let you find it still but what I can tell you is that $k>3$. So \begin{align}k!+3k^2+3k+1 &< k!+(k)k^2+(k^2)k+(k^3)\cdot 1 \\ &= k! + 3k^3 \\ &<k! + k\cdot k^3 \\ &<k! + k\cdot k! \tag{Induction Hypothesis} \\ &= k!(k+1) \\ &= (k+1)! \end{align}

• whoops, should of noticed the backwards inequality, had it the right way on paper. kudos – Xian Oct 6 '15 at 3:43
• @Xian It happens :) I have edited my post as well. Do you understand my series of inequalities? – graydad Oct 6 '15 at 3:45
• yes, the answer makes sense (I figured the next steps were to replace the 3s with k's then simplify), I'm not totally sure on how to find a algebraically though. – Xian Oct 6 '15 at 3:58
• @Xian Honestly the algebra to do that would be some insane shit. Solving $x! = x^3$in closed form by hand might even be outright impossible. Guess and check to find $a$ or plug into a calculator $x! = x^3$. The first integer greater than or equal to $x$ is your $a$. – graydad Oct 6 '15 at 4:01
• point taken. thanks for all the help guys. our professor is no good at teaching this stuff, but luckily you guys are. – Xian Oct 6 '15 at 4:21

Check the first number: $4! = 24 < 4^3 = 64$; $5! = 120 < 5^3 = 125$.

Now, $6! = 720 > 6^3 = 216$.

Assume that $k! > k^3$ for $k>5$. We need to prove that $(k+1)! > (k+1)^3$.

Firstly, we prove that $k^3 > (k+1)^2$. Indeed, we have $(k-1)^3 > 0$, then $k^3> 3k^2 - 3k + 1 > k^2 + 2k + 1 = (k+1)^2$.

So, we get $(k+1)! > k^3(k+1) > (k+1)^3$.

• For me, $k! > k^3$ for $k > 5$ is not different than $k! > k^3$ for all $k > 5$. But maybe it is because I am not a native english speaker. – Éric Guirbal Oct 6 '15 at 3:31

Claim: $n!>n^3$ for all $n\geq 6$

Base case: For $n=6$ we have $n!=720>216=6^3$

Let us assume for our induction hypothesis that there is some $k\geq 6$ such that $k!>k^3$. We want to show that it is also true for $k+1$.

(here you should not begin with $(k+1)!>k^3$ and try to reach a tautology. This should instead be the final line/conclusion)

$(k+1)! = (k+1)(k!)>^{\text{I.H.}}(k+1)k^3 >^{(\dagger)} (4)k^3 =k^3+k^3+k^3+k^3> k^3+3k^2+3k+1=(k+1)^3$

where $\text{I.H.}$ denotes where we applied the induction hypothesis and the step at $(\dagger)$ is because $k>3$ we can say $k+1>4$.

• how would one go about finding a without plugging in numbers manually? I'm guessing you set a! = n^3, but not sure where to go after that – Xian Oct 6 '15 at 3:54
• To be honest, I looked at the graph of $f(n)=n!-n^3$ and found where it became positive. – JMoravitz Oct 6 '15 at 3:56