How to show that $\frac{n!}{n^{\frac{n}{2}}}$ diverges as $n \to \infty$?

Question

The exact question is, is it true or not that

$$ n! = O(n^{\frac{n}{2}}) $$

I tried a few values of $n$ and guessed that it does not (this is obviously not very proper mathematics).

I applied the definition, i.e. I want to show that there does not exist an $N$ such that for all $n > N$ it is the case that

$$ n! \leqq c \cdot n^{\frac{n}{2}} $$

I had two ideas as to how to proceed,

1. carry out a proof by contradiction (i.e. assuming that this $N$ does exist, but I wasn't able to derive an absurdity). I tried something along the lines of

Assume there exists an $N$ and a $c \in \mathbb{R}$ such that for all $n > N$ it is the case that $$ n! \leqq c\cdot n^{\frac{n}{2}} $$

Then it is also the case that because

$$ n! \geqq \left(\frac{n}{2}\right)^{\frac{n}{2}} $$

Therefore,

$$ \left(\frac{n}{2}\right)^{\frac{n}{2}} \leqq n! \leqq c \cdot n^{\frac{n}{2}} $$

But this does not help, because $\left(\frac{1}{2}\right)^{\frac{n}{2}}$ just tends to 0.

I thought that I could try to use a bigger lower bound, i.e. something in the form $(an)^{\frac{n}{2}}$ where $a > 1$, but I'm not sure how to prove this exists.

2. try to pair up items on the left and right-hand sides and show that each item on the left-hand side (e.g. for showing that $n! = O(n^n)$ as there are the same number of terms on the left and right hand side it is possible to cancel them out.

Any help is greatly appreciated!

Answer 1

I tried a few values of $n$ and guessed that it does not (this is obviously not very proper mathematics).

This is completely proper mathematics! Of course if you want to get a handle on what's going on you should look at specific values of $n$. Many posters on math.SE would be able to answer their own questions if they did this.

Anyway, this can be done using the following simple version of Stirling's approximation, which I learned from Terence Tao. Starting from the identity $e^x = \sum_{n \ge 0} \frac{x^n}{n!}$, it follows that for $x \ge 0$ we have $e^x \ge \frac{x^n}{n!}$ for all non-negative integers $n$, hence that

$$n! \ge \frac{x^n}{e^x}$$

for all real $x \ge 0$. To get as good a bound using this as possible we want to choose $x$ such that the RHS is as large as possible. We can figure out what value of $x$ this is by taking the logarithm, then the derivative, then setting this equal to zero; the logarithm is $n \log x - x$ and its derivative is $\frac{n}{x} - 1$, so we get $x = n$, and hence the best possible bound we can get using this inequality is

$$\boxed{ n! \ge \frac{n^n}{e^n} }.$$

Now it's easy to see that $\frac{n!}{n^{\frac{n}{2}}} \ge \frac{n^{\frac{n}{2}}}{e^n}$ goes to infinity, since for example once $n \ge 9$ we have $n^{\frac{n}{2}} \ge 9^{\frac{n}{2}} = 3^n$.

This is probably the simplest nontrivial example of a saddle point bound; the more general saddle point bound has many applications to figuring out the asymptotics of sequences more complicated than the factorials.

Answer 2

Stirling (see wikipedia) would help you but that's no fun.

Try to pair terms together $n!$ to form products that are all larger than $n$. Then you just need one pair to be of order larger than $n$ for the whole thing to be of order larger than $n^{n/2}$.

Edit : did not see that you already suggested that in your question. It works. Spoilers under the line

---

Basically you can show that

$n \times 1 \geq n$,

$(n-1)\times 2 \geq n$

and so on, moreover the central product $n/2 \times (n/2+1) \geq n^2/4$.

You can then deduce $\dfrac{n!}{n^{n/2}} \geq n/4$.

Answer 3

Since $$a_n=\frac{n!}{n^{\frac{n}{2}}}$$ Is a positive sequence and has a factorial in it, we usually use the ratio test. we find that $$\frac{a_{n+1}}{a_{n}}=\left(\frac{(n+1)!}{n!}\right)\left(\frac{n^{\frac{n}{2}}}{(n+1)^{\frac{n+1}{2}}}\right)$$ $$=(n+1)\left(\frac{n^{\frac{n}{2}}}{(n+1)^{\frac{n+1}{2}}}\right)$$ $$=(n+1)^\frac{1}{2}\left(\frac{n}{n+1}\right)^\frac{n}{2}$$ $$=(n+1)^\frac{1}{2}\left(\left(\frac{n}{n+1}\right)^n\right)^\frac{1}{2}$$

and given that $$\lim_{n\to +\infty}\left(\frac{n}{n+1}\right)^n=e^{-1}$$ we get that $$\lim_{n\to +\infty} \frac{a_{n+1}}{a_{n}}$$ $$=\lim_{n\to +\infty} (n+1)^\frac{1}{2}\left(\left(\frac{n}{n+1}\right)^n\right)^\frac{1}{2}$$ $$=\lim_{n\to +\infty} (n+1)^\frac{1}{2}e^{-\frac{1}{2}}=+\infty$$

Hence, and according to the ration test, the series is divergent which forces the sequence itself to be divergent.

Answer 4

No need to Stirling's approximation formula. By a property of Gamma function,

$$n!=\Gamma(n+1)=\int_0^{\infty}x^ne^{-x}dx>\int_n^{\infty}x^ne^{-x}dx>\int_n^{\infty}n^ne^{-x}dx>n^ne^{-n},$$ therefore $\frac{n!}{n^{\frac{n}{2}}}=\frac{n^{\frac{n}{2}}}{e^n}\rightarrow\infty.$