solucionar $\ln(n!) = \Theta(n\ln(n))$ sin aproximación de stirling

Question

Mi tarea fue probar esta ecuación es simple usando la aproximación de Stirling. Me preguntaba si hay algún otro método para demostrar que - sin Stirling- Puedo probarlo $\ln(n!) = O(n\ln(n))$ como este: $$\ln(n!)=\ln(n\cdot(n-1)\cdots2\cdot1)=\ln(n)+\ln(n-1)+\cdots+\ln(2)+\ln(1)≤n\ln(n) , que es obviuos.

Pero no puedo demostrar que $\ln(n!) = \Omega(n\ln(n))$.

por favor, ayudar. gracias :)

Answer 1

El uso de un multiplicativo variante de Gauss del truco: $$(n!)^2 = (1 \cdot n) (2 \cdot (n-1)) (3 \cdot (n-2)) \cdots ((n-2) \cdot 3) ((n-1) \cdot 2) (n \cdot 1) \ge n^n$$ Esto implica que $\ln(n!) \ge \dfrac12 n \ln n$.

La otra dirección es fácil, como usted menciona, porque $n! \le n^n$$\ln(n!) \le n \ln n$.

Por lo $\dfrac12 n \ln n \le \ln(n!) \le n \ln n$$\ln(n!) = \Theta(n\ln(n))$.