# Showing n! is greater than n to the tenth power

I'd like to show $n!>n^{10}$ for large enough n ( namely $n \geq 15$).

By induction, I do not know how to proceed at this step:

$$(n+1)\cdot n!>(n+1)^{10}$$

As I can't see how to simplify $(n+1)^{10}$.

This seems like such a trivial thing (and it probably is), yet I can't do it. Isn't there an easier way to show this?

(P.S. I need to refrain from the use of derivatives, integrals etc., I suppose, then you could work something out with the slope of the respective functions)

• It almost works for n=1: 1! = 1, 1^10 = 1*1*1*1*1*1*1*1*1*1 = 1, it is an infinitesimal amount short of being greater! – OldBunny2800 Dec 2 '16 at 3:22
• @OldBunny2800: and for $n=2$, we have $2! = 2$, while $2^{10} = 1024$. So modulo a finite initial segment, $2!$ is greater than $2^{10}$. – Peter LeFanu Lumsdaine Dec 2 '16 at 15:29
• – Martin Sleziak Dec 2 '16 at 16:16

You need to work in the fact that $n! \gt n^{10}$ as that is the heart of the induction. So for $n \gt 15$ $$\text {Base case } 15!-15^{10}=731023977375 \gt 0\\ \text {Assume }n! \gt n^{10}\\(n+1)! =(n+1)n!\gt (n+1)n^{10}=(n+1)^{10}\frac {n^{10}}{(n+1)^9}$$ Now we need to argue that the last fraction on the right is greater than $1$ and we are home.

$$\frac {n^{10}}{(n+1)^9} = n\left(1-\frac 1{n+1}\right)^9\gt n\left(1-\frac 9{n+1}\right)\gt 15\cdot \frac 7{16}\gt 1$$

• Could you please elaborate, how you got to $(n+1)n^{10}$ ? Should it not be $(n+1)^{10}$ ? – Jonathan Dec 1 '16 at 22:51
• I just multiplied the first inequality by $n+1$ on both sides. That gave me $(n+1)!$ on the left like I wanted. Now I need to show that the right is greater than $(n+1)^{10}$, which is what I do with the rest. – Ross Millikan Dec 1 '16 at 22:56
• I see now, I didn't read your post properly, I apologise – Jonathan Dec 1 '16 at 22:56
• So, $(\frac{7}{16})^{9} > \frac{7}{16}$? – Atomosk Dec 2 '16 at 6:12
• @Atomosk: No, but $(\frac {15}{16})^9 \gt \frac 7{16}$. That is what I claimed. – Ross Millikan Dec 2 '16 at 6:15

Since it's needed, here's the base case of $15! > 15^{10}$ without (much) calculation:

$15! = 2^{7}\cdot 2^{3}\cdot{2}\cdot 3^{5}\cdot{3}\cdot 5^{3}\cdot 7^2\cdot 11\cdot 13 \\ \phantom{15!} = 2^{11}\cdot 3^{6}\cdot 5^{3}\cdot 7^2\cdot 11\cdot 13 \\ \phantom{15!} = 16^2\cdot 15^3\cdot 18 \cdot (14\cdot 21)\cdot (22\cdot13) \\ \phantom{15!} > 15^2\cdot 15^3 \cdot 15\cdot 15^2\cdot 15^2 = 15^{10}$

Remember to show the base case, namely that $15! > 15^{10}$. After that is verified, make the induction hypothesis (IH):

IH: $m! > m^{10}$

Show: $(m+1)! > (m+1)^{10}$ using IH.

As you've done so far, what we need to show is: \begin{align} (m+1)! = (m+1)m! > (m+1)^{10} \end{align}

Also note that $(m+1)^{10} = (m+1)(m+1)^9$. So, cancelling the ''$m+1$'' terms, we need to show $m! > (m+1)^9$ using the fact that $m! > m^{10}$.

Finally, notice that if we can show that $m^{10} > (m+1)^9$ then we are done. Equivalently, we just need to show that $\frac{m^{10}}{(m+1)^9} > 1$. I'll leave this up to you.

This is just a fun observation: $$(n!)^2= \prod_{i=1}^n i(n+1-i)>n^n$$ so at least for $n\geq 20$ we have $\sqrt{(n!)^2}=n!>n^{n/2}\geq n^{10}$. Given this, we would only need to account for the cases $n=15,...,19$. But this is not an inductive approach, of course.

• Your 2k agrees with mine as a nice elementary bound. But your proof is simpler. – marty cohen Dec 1 '16 at 23:54
• @martycohen: Yes, the $2k$ was what I had in mind too :o) – String Dec 1 '16 at 23:59

Let $n\geq 15$ such that

$$n!\geq n^{10}$$

we want that

$$(n+1)!=(n+1)n!\geq(n+1)n^{10}$$

$$\geq (n+1)^{10}$$

which means that we want to prove

$$n\geq (1+\frac 1n)^9$$

or

$$n^{\frac{n}{9}}\geq (1+\frac 1n)^n$$

and this is true for large enough $n$ cause the sequence on the left goes to $+\infty$, while the sequence on the right goes to $e$.

The handiest inequalities for $n!$ are $(n/e)^n < n! < (n/e)^{n+1}$.

These are easily proved by induction from $(1+1/n)^n < e < (1+1/n)^{n+1}$, and these have been proved here a number of times.

From $n! > (n/e)^n$, to show that $n! > n^k$ for large enough $n$, it is enough to show that $(n/e)^n > n^k$ for large enough $n$.

$(n/e)^n > n^k \iff n^{n-k} > e^n \iff n^{1-k/n} > e$.

If you are not worrying about getting the best possible bound, take $n > 2k$. Then $n^{1-k/n} > n^{1/2} > (2k)^{1/2} \gt e$ for $2k > e^2$.

If $2k < e^2$, choose $n > \max(2k, e^2)$.

Therefore, if $n > \max(2k, e^2)$ then $n! > n^k$.

There's no need for induction or anything beyond elementary arithmetic. For $n\geq 15$, \begin{align*} n!&\geq n(n-1)\cdots(n-9)\times 5\cdot 4\cdot 3\cdot 2 \\ &= 120n(n-1)\cdots(n-9)\\ &> n \cdot \frac{15}{14}(n-1)\cdot \frac{15}{13}(n-2)\cdots \frac{15}{6}(n-9)\\ &\geq n^{10}\,, \end{align*} where the strict inequality is because the third line is approximately $53n(n-1)\cdots(n-9)$ and the final inequality is because, for all $i$ and $n$ with $1\leq i<15\leq n$, $$\frac{15}{15-i}(n-i) = n + \frac{(n-15)i}{15-i} \geq n\,.$$

Replacing $n$ by $n+1$, the LHS is multiplied by $n+1$ while the RHS is multiplied by $\left(1+\frac1n\right)^{10}$, which is bounded (by $1024$ for $n\ge1$, but by $2$ for $n\ge15$).