Cómo probar esta aproximación del logaritmo del factorial

Question

En otras palabras, cómo probar esta ecuación

$$\lg{n!} = \Theta(n\lg{n})$$

Answer 1

Una pista: $$ n\log \bigg(\frac{n}{e}\bigg) + 1 \le \log n! \le (n + 1)\log \bigg(\frac{{n + 1}}{e}\bigg) + 1. $$ Tomado de Wikipedia, véase aquí .

EDIT: En realidad se dice en ese enlace "Por lo tanto $\log n!$ es $\Theta (n\log n)$ ''.

EDIT 2: La derivación del resultado anterior se da en el enlace de Wikipedia (y es muy elemental). Basándonos en ella, demostremos que $$ \log n! = n \log n - n + O(\log n) \;\; {\rm as}\; n \to \infty, $$ lo que implica, en particular, que $$ \log n! \sim n\log n \;\; {\rm as}\; n \to \infty $$ (es decir, $\log n! / (n\log n) \to 1$ como $n \to \infty$ ), lo que implica, en particular, que $\log n!$ es $\Theta (n\log n)$ . Por lo tanto, primero hay que tener en cuenta que $$ n\log n - n + 1 \le \log n! \le (n + 1)\log (n + 1) - (n + 1) + 1. $$ Por lo tanto, $$ n\log n - n + 1 \le \log n! \le n\log (n + 1) + \log (n + 1) - n. $$ A continuación, observe que, dado que $\log(1+x) = x + O(x^2)$ como $x \to 0$ , $$ \log(n+1) - \log n = \log \bigg(\frac{{n + 1}}{n}\bigg) = \log \bigg(1 + \frac{1}{n}\bigg) = \frac{1}{n} + O\bigg(\frac{1}{{n^2 }}\bigg), $$ y por lo tanto $$ \log(n+1) = \log n + \frac{1}{n} + O\bigg(\frac{1}{{n^2 }}\bigg). $$ Ahora, $$ n\log n - n + 1 \le \log n! \leq n\bigg[\log n + \frac{1}{n} + O\bigg(\frac{1}{{n^2 }}\bigg)\bigg] + \bigg[\log n + \frac{1}{n} + O\bigg(\frac{1}{{n^2 }}\bigg)\bigg] - n, $$ por lo que $$ n\log n - n + 1 \le \log n! \leq n\log n - n + \log n + O(1), $$ y finalmente $$ \log n! = n \log n - n + O(\log n). $$

Answer 2

La parte fácil es $\log(n!) \le n \log n$ que se deduce de $n! \le n^n$ .

La parte difícil se discute en ¿Cómo se demuestra que $n^n$ es $O(n!^2)$ ? .

Answer 3

$e^x = \sum_{n \ge 0} \frac{x^n}{n!}$ implica $e^n \ge \frac{n^n}{n!}$ Por lo tanto $n! \ge \left( \frac{n}{e} \right)^n$ Por lo tanto $\log n! \ge n \log n - n$ . Por otro lado,

$$n! \le \left( \frac{1 + 2 + ... + n}{n} \right)^n = \left( \frac{n+1}{2} \right)^n$$

por AM-GM Por lo tanto $\log n! \le n \log \left( \frac{n+1}{2} \right)$ .

Answer 4

Mirando el gráfico de $\log$ se verifican inmediatamente las desigualdades $$\int_1^n\log x\ dx <\sum_{k=1}^n\log k<\int_2^{n+1}\log x\ dx\ .$$ Evaluando las integrales se obtiene $$n\log n -n+1< \log(n!)<(n+1)\log(n+1)-n + c$$ con $c=1-\log 4$ y esto implica fácilmente ${\log(n!)\over n\log n}\to 1$ $(n\to\infty)$ .