Una pregunta sobre la aproximación de Stirling, y $\log(n!)$

Question

En el análisis de un algoritmo de esta declaración ha llegado hasta:$$\sum_{k = 1}^n\log(k) \in \Theta(n\log(n))$$ and I am having trouble justifying it. I wrote $$\sum_{k = 1}^n\log(k) = \log(n!), \ \ n\log(n) = \log(n^n)$$ and it is easy to see that $\log(n!) \en O(\log(n^n))$, but the "$\Theta$" part is still perplexing. I tried calculating the limit: $$\lim_{n \to\infty} \frac{\log(n!)}{\log(n^n)}$$but the only way that I thought of doing this was to substitute the Stirling approximation in the numerator, and it works, but this would only be justified if $$\lim_{n \to\infty}\frac{\log(n!)}{\log(\sigma(n))} = 1$$(with $\sigma(n) = \sqrt{2\pi} \cdot n^{\frac{1}{2} + n} \cdot e^{-n} $) and is it? It is certainly wrong that $$a_n \sim b_n \ \Rightarrow \ f(a_n) \in \Theta(f(b_n))$$ for a general (continuous) $f : \mathbb{R} \rightarrow \mathbb{R}$, since, for example, $a_n =n^2+n, b_n=n^2$ and $f(x) = e^x$ is a counterexample (since $\frac{n^2 + n}{n^2} \rightarrow 1$, but $ \frac{e^{n^2+n}}{e^{n^2}} \rightarrow +\infty$). Así que aquí están mis preguntas:

1. Es la afirmación verdadera, bajo ciertas hipótesis en $f$ (por ejemplo, $f \in O(x)$ sería plausible), y, en particular, en el caso de la $f(x) = \log(x)$?
2. Si no, ¿cómo puedo proceder en la prueba inicial, el uso de Stirling, o de otra manera?

No sé (y no quieres usar nada andvanced en la aproximación de Stirling, tales como las estimaciones de error; yo sé que $n! = \sigma(n)(1+ O(\frac{1}{n}))$, y no mucho más.

Cualquier ayuda es muy apreciada. Gracias.

Answer 1

He aquí otra respuesta a la pregunta 2. Por el Stolz–Cesàro teorema,

$$\lim_{n\to\infty}\frac{\log(n!)}{\log(n^n)}=\lim_{n\to\infty}\frac{\log(n+1)}{\log(n+1)+\log\left(\left(1+\frac{1}{n}\right)^n\right)}=1.$$

---

Para una respuesta parcial a la pregunta 1, he aquí una manera de ver que $a_n\sim b_n$ implica $\log(a_n)\sim\log(b_n)$ (bajo hipótesis razonables como $|\log(b_n)|>\varepsilon$ fijos $\varepsilon>0$ y suficientemente grande $n$). Tenga en cuenta que

$$\frac{\log(a_n)}{\log(b_n)}=\frac{\log(b_n)+\log\left(\frac{a_n}{b_n}\right)}{\log(b_n)}.$$

Esto también implica que si $a_n\in\Theta(b_n)$$|\log(b_n)|\to\infty$,$\log(a_n)\sim \log(b_n)$.

Answer 2

Bien, permite trabajar las matemáticas.

Por el trapecio, regla de, $\ln n! \approx \int_1^n \ln(x)\,{\rm d}x = n \ln n - n + 1$. Ahora nos encontramos con el error en la aproximación, en la que uno puede calcular por Euler–Maclaurin de la fórmula. Después de algunos crudo de la aritmética, se puede calcular que

$$ \ln (n!) - \frac{\ln n}{2}= n \ln n - n + 1 + \sum_{k=2}^{m} \frac{\mathcal{B}_k\,(-1)^k}{k(k-1)} \left( \frac{1}{n^{k-1}} - 1 \right) + S_{m,n}, $$ where $\mathcal{B}_k$ denota la de Bernoulli del número.

Ahora tomando límites, se puede calcular $$\lim_{n \to \infty} \left( \ln n! - n \ln n + n - \frac{\ln n}{2} \right) = 1 - \sum_{k=2}^{m} \frac{\mathcal{B}_k(-1)^k}{k(k-1)} + \lim_{n \to \infty} S_{m,n}$$.

Ahora desde $S_{m,n}$ satisface la siguiente propiedad, $$S_{m,n} = \lim_{n \to \infty} S_{m,n} + O \left( \frac{1}{n^m} \right),$$ we get the approximation in the logarithmic form. Taking exponent on both the sides and plugging $m=1$, obtenemos el resultado: $$n! = \sqrt{2 \pi n}~{\left( \frac{n}{e} \right)}^n \left( 1 + O \left( \frac{1}{n} \right) \right).$$

Si usted no se preocupe de la $\sqrt{2 \pi n}$ plazo, supongo que sólo puede utilizar la aproximación $\ln n! \approx \sum_{j=1}^n \ln j$ como sigue:

$$\sum_{j=1}^n \ln j \approx \int_1^n \ln x \,{\rm d}x = n\ln n - n + 1 = \Theta(n \ln n)$$.

Answer 3

Poner $s_n:=\sum_{k=1}^n\ln k$. A continuación, $s_n\leq n\ln n$ $$s_n=\sum_{k=1}^n\log (n-k+1)=n\log n+\sum_{k=1}^n\log\left(1-\frac{k-1}n\right)$$ y el uso de $\log(1+t)\geq t-t^2/2$ tenemos
\begin{align*} s_n&\geq n\log n-\sum_{j=0}^{n-1}\frac jn+\frac{j^2}{2n^2}\\ &=n\log n-\frac{n-1}2-\frac{(n-1)(2n-1)}{6n}\\ &=n\log n-\frac{n-1}{2n}\left(n+\frac{2n-1}3\right)\\ &=n\log n-\frac{n-1}2\frac{5n-1}{3n}\\ &=n\log n-\frac{n-1}6\left(5-\frac 1n\right), \end{align*} por lo $$\frac{s_n}{n\log n}\geq 1-\left(1-\frac 1n\right)\frac 1{6\log n}\left(5-\frac 1n\right),$$ que está por debajo de acotado por una constante positiva, por ejemplo, $\frac 12$ $n$ lo suficientemente grande.

Answer 4

Una respuesta a la pregunta 1. implica lentamente/regularmente diferentes funciones, cuyo estudio es, a veces, se resumen como Karamata la teoría. Lentamente diferentes funciones son funciones positivas $L$ tal que, para cada positivos $\lambda$, $L(\lambda x)/L(x)\to1$ al $x\to+\infty$.

A ver que tal de las funciones que la implicación en la pregunta 1. cierto, supongamos que $f$ es poco a poco diferentes, y además, para simplificar las cosas, que $f$ es no decreciente. Entonces, si $a_n\sim b_n$ y $a_n,b_n\to+\infty$, $\frac12a_n\leqslant b_n\leqslant 2a_n$ para cada $n$ lo suficientemente grande, por lo tanto $$ \frac{f(\frac12a_n)}{f(a_n)}\leqslant \frac{f(b_n)}{f(a_n)}\leqslant \frac{f(2a_n)}{f(a_n)}. $$ Desde el límite inferior y el límite superior de ambos convergen a $1$, esto demuestra que $f(a_n)\sim f(b_n)$.

Gracias a Karamata del teorema de caracterización, el mismo tipo de argumento puede aplicarse a la categoría más amplia de regularmente diferentes funciones. Estas son funciones positivas $L$ tal que, para cada positivos $\lambda$, $L(\lambda x)/L(x)$ tiene un finito positivo límite al $x\to+\infty$.

De ahí la implicación: $a_n\sim b_n$ implica $f(a_n)\sim f(b_n)$ si $a_n,b_n\to+\infty$, se tiene para cada regularmente variación de la función $f$.

Ejemplos de lenta variación de funciones de los poderes de la $\log(x)$. Ejemplos de forma regular diferentes funciones de los poderes de la $x$ (posiblemente, a veces lentamente variación de la función). Ejemplos de no regularmente diferentes funciones son las exponenciales de los poderes de $x$ (posiblemente, a veces regularmente variación de la función).