Proving $n^{n/2} = \mathcal{O}(n!)$ Without Stirling's Approx

[alyafey22]

I wanted to prove that

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

I used the Striling approximation but I don't think my teacher will be happy to see that. Can you suggest another approach that is more elementary.

 

[I like Serena]

I wanted to prove that

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

I used the Striling approximation but I don't think my teacher will be happy to see that. Can you suggest another approach that is more elementary.

Consider the derivation of Stirling's approximation.
It consists of first taking the logarithm, and then finding lower and upper integrals for $\sum_{j=1}^n \ln j$.
It is fairly straight forward and can be applied here as well.So what you want to prove is that there are some $C$ and $N$ such that for each $n>N$:
$$\frac n 2 \ln n \le \ln(C n!) = \ln C + \sum_{j=1}^n \ln j$$

This follows if we can prove that:
$$\frac n 2 \ln n \le \ln C + \int_1^n \ln x\,dx = \ln C + n\ln n - n + 1$$

 

[Evgeny.Makarov]

I wanted to prove that

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

\[
\frac{n^{n/2}}{n!}\le\frac{2^{n/2}}{(n/2)!}\le 1\text { if }n/2>3.
\]