Prove or disprove $n! \in O(n^{n-2})$

Question

Prove or disprove $n! \in O(n^{n-2})$

I think that the statement is true so I tried calculating the limit.

So I have to calculate the limit.

$$\lim_{n\to \infty} \frac{n!}{n^{n-2}}=\lim_{n\to\infty} \frac{n!n^2}{n^{n}}$$

After that i tried substituting Stirlings approximation but it didn't end well. Could I please get some help?

Answer 1

Notice that $$\frac{n!}{n^n}=(\frac{1}{n})(\frac{2}{n})(\frac{3}{n})\cdots (\frac{n}{n})\leq (\frac{1}{n})(\frac{2}{n}))=\frac{2}{n^2}$$

since each term $\frac{i}{n}\leq 1$ for $1\leq i \leq n$.

So $$n! \leq 2n^{n-2}$$

and your statement follows. (Thanks to user Clement. C for all their help editing this answer =) )

Answer 2

Most direct proof I can think of:

Write $$ n! = \Pi_{k=1}^n k = 1\cdot 2 \cdot \Pi_{k=3}^n k \leq 1\cdot 2 \cdot \Pi_{k=3}^n n = 2n^{n-2} $$

Can you conclude?

Answer 3

$n^{n-2}$ is the number of spanning trees of $n$ vertices, and $\frac{n!}{2}$ is the number of ways you can label the linear graph with $n$-vertices by numbers $\{1, \cdots, n\}$, each number being used only once. So $n! = O(n^{n-2})$.

Answer 4

By ratio test

$$\frac{a_{n+1}}{a_n}=\frac{(n+1)!(n+1)^2}{(n+1)^{n+1}}\cdot\frac{n^n}{n!n^2}=\frac{(n+1)^2}{n^2}\left(\frac{n}{n+1}\right)^n=\frac{(n+1)^2}{n^2}\frac{1}{\left(1+\frac1n\right)^n}\to \frac1e<1$$

then $$a_n\to 0$$

Answer 5

A small improvement: $n!=o(n^{n-2})$.

Set $k:=\lfloor n/2\rfloor$. Then \begin{align} n! &\le (2k+1)!=k\prod_{i=1}^k (k+1+i)(k+1-i) \\ &\le (k+1)\prod_{i=1}^k (k+1)^2 = (k+1)^{2k+1} \le \left(\frac{n+1}{2}\right)^{n+1}. \end{align} Hence $$ \frac{n!}{n^{n-2}} \le \frac{\left(\frac{n+1}{2}\right)^{n+1}}{n^{n-2}} \le \frac{(2n/3)^{3n/2}}{n^{n-2}} \le \left(\frac{2}{3}\right)^{3n/2}n^{\frac{n}{2}-2} \to 0. $$