How would you prove $n! ∈ Ω(n^{n/2})$ ? This example was given to us in school, but I don't know how to prove it.
What I'am trying to prove: \begin{align} n! ∈ Ω(n^{n/2}) ⇔ ∃ c ∈ ℝ^+,\ ∃ n_0 ∈ ℕ^+,\ ∀ n ≥ n_0 : cn^{n/2} ≤ n! \end{align}
What I tried was induction:
1) \begin{align} n=1, c=1: √1 ≤ 1 \end{align}
2) \begin{align} (cn^{n/2} ≤ n!) ⇒ c(n+1)^{(n+1)/2} ≤ (n+1)!\\ c(n+1)^{((n+1)/2)-1}(n+1)≤ (n+1)n!\\ c(n+1)^{((n+1)/2)-1} ≤ n! \end{align}
This is the part where I get stuck and don't know how to end the proof.
Thank you for response.
I am not that familiar with these kinds of proofs but I would suggest, as pointed out within the comments, to use Stirling's approximation for the factorial here. This can be seen as an extended comment since my argumentation is not completely sufficient.
We want to show that $cn^{n/2}\le n!$ for $n$ greater than some $n_0$. Lets consider Stirling's approximation and do a little bit of reshaping on it.
$$n!\sim\sqrt{2\pi n}\left(\frac ne\right)^n=\frac{\sqrt{2\pi}}{e^n}n^{n+\frac12}$$
where the term infront of the power of $n$ is just a dercreasing term as $n$ goes up to infinity. Reconsider our given inequality and plug in the final form of Stirling's approximation
$$\begin{align} cn^{n/2}&\le n!\\ &=\frac{\sqrt{2\pi}}{e^n}n^{n+\frac12}\\ cn^{n/2}&\le\underbrace{\frac{\sqrt{2\pi}}{e^n}}_{\approx k}n^{n+\frac12} \end{align}$$
The marked term $k$ can be seen as a constant in some way. I am not sure how to argue about this in a proper way to be honest. But nevertheless this leaves us with
$$\begin{align} cn^{n/2}&\le k n^{n+\frac12} \end{align}$$
from which one we can conclude that the RHS is bigger than the LHS side depending on a constant $l=\frac ck$.