Usaremos el hecho de que
[matemáticas] \ ln (a) + \ ln (b) = \ ln (a * b) [/ matemáticas]
Entonces:
[matemáticas] \ sum_ {i = 1} ^ n \ ln (\ frac {n} {i}) = \ ln (\ prod_ {i = 1} ^ n \ frac {n} {i}) [/ math]
- Cómo resolver T (n) = 2T (n / 2) + log n con el método del árbol de recurrencia
- La hipótesis de Riemann establece que [math] \ pi (n) – li (n) \ sim n ^ {1/2} \ log n [/ math]. Sin embargo, ¿implica que sea el comportamiento asintótico más estricto posible? ¿Puede haber una función [matemáticas] f (n) <n ^ {1/2} \ log n /; lim_ {n \ to \ infty} \ frac {\ pi (n) -li (n)} {f (n)} = K [/ matemáticas]? es decir: [matemáticas] f (n) = \ sqrt {n} [/ matemáticas]
- ¿Cómo podemos calcular la frecuencia y el peso de los errores incurridos por múltiples personas que realizan una tarea repetible?
- ¿Cómo podría obtener los números primos entre un rango de (1) a (n) en la raíz cuadrada de N?
- ¿Qué número n tiene la mayoría de los factores en comparación con todos los números menores que n?
[matemáticas] = \ ln (\ frac {n ^ n} {n!}) [/ matemáticas]
Ahora usaremos el mismo hecho a la inversa
[matemáticas] \ ln (a * b) = \ ln (a) + \ ln (b) [/ matemáticas]
[matemáticas] \ ln (\ frac {n ^ n} {n!}) = \ ln (n ^ n) – \ ln (n!) = n * \ ln (n) – \ ln (n!) [/ matemáticas]
No hay una forma cerrada fácil para [math] \ ln (n!) [/ Math], pero hay una muy buena aproximación conocida como aproximación de Stirling [1]
La aproximación de Stirling es [matemática] \ ln (n!) \ Aprox n * \ ln (n) – n + O (\ ln (n)) [/ matemática]
Conectando eso de nuevo, obtenemos
[matemáticas] \ sum_ {i = 1} ^ n \ ln (\ frac {n} {i}) \ aprox n * \ ln (n) – (n * \ ln (n) – n) [/ matemáticas]
[matemáticas] \ sum_ {i = 1} ^ n \ ln (\ frac {n} {i}) \ aprox n [/ matemáticas]
Una aproximación un poco más precisa sería
[matemáticas] \ sum_ {i = 1} ^ n \ ln (\ frac {n} {i}) \ aprox n- \ frac {1} {2} \ ln (2 \ pi * n) [/ matemáticas]
Notas al pie
[1] Aproximación de Stirling – Wikipedia