How to show that $\frac{n!}{n^{\frac{n}{2}}}$ diverges as $n \to \infty$? 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,

*

*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.


*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!
 A: 
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.
A: 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$.
A: 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.
A: 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.$
