Cómo Utilizar la Notación Big O

Question

En mi pregunta acerca de la convergencia/divergencia de

$$ \sum_{n=2}^\infty \frac{1\cdot 3\cdot 5\cdot 7\cdots (2n-3)}{2^nn!}. $$

aquí: ¿por Qué no en Esta Serie Converge?

Zarrax dio la respuesta:

"Puede utilizar aproximaciones de Taylor aquí. Tenga en cuenta que la relación entre términos consecutivos es ${2n - 3 \over 2n} = \exp(\ln(1 - 3/2n)) = \exp(-{3 \over 2n} + O(1/n^2))$. Por lo que el producto es comparable a $\exp(-{3 \over 2} \sum_{i = 2}^n {1 \over n} + O(1/n))$, que es comparable a $\exp(-{3 \over 2} \ln(n))$ o $n^{-{3 \over 2}}$. Por lo tanto la serie converge."

Me he decidido a dar una charla en un seminario de posgrado sobre el peligro de venir para arriba con ejemplos la parte superior de tu cabeza y ahora desea entender lo que esta respuesta significa. El problema es que no tengo la menor exposición a la notación big O y no estoy teniendo suerte en línea. Básicamente, no entiendo la respuesta. Me pueden romper en un par de preguntas:

1. ¿Cómo Zarrax pasar de $\exp(\ln(1 - 3/2n))$$\exp(-{3 \over 2n} + O(1/n^2))$?

2. El producto que se está Zarrax refiriéndose en su tercera frase? Y ¿cómo es comparable a $\exp(-{3 \over 2} \sum_{i = 2}^n {1 \over n} + O(1/n))$?

3. ¿Cómo Zarrax pasar de eso a $\exp(-{3 \over 2} \ln(n))$?

Gracias por su ayuda.

Answer 1

Para responder a tus preguntas:

1) es el uso de $\log(1-x) = -x-x^2/2-x^3/3 - \cdots = -x + O(x^2).$

2) El producto al que se refiere es $$\frac{1\cdot 3\cdot 5\cdot 7\cdots (2n-3)}{2^nn!}$$

y es comparable a $\exp(-{3 \over 2} \sum_{i = 2}^n {1 \over n} + O(1/n))$ debido a que este es el producto de $n-1$ versiones de $\exp(-{3 \over 2n} + O(1/n^2)).$

3) Se usa $\sum_{i=2}^n 1/i = \log n + \text{constant} + O(1/n).$

Answer 2

Cuando una expresión se usa $\mathcal{O}(1/n^2)$ significa que es en realidad una función de $f$ tal que $f \in \mathcal{O}(1/n^2)$. Este es un muy conveniente abuso de notación.

Tenga en cuenta que $\mathcal{O}(1/n^2)$ es en realidad un conjunto de funciones. Una función de $f \in \mathcal{O}(1/n^2)$ fib hay una constante $C$ (dependiendo de la $f$) tal que $|f(n)| \le \frac{C}{n^2}$ para todos lo suficientemente grande $n$, es decir, como $n \to \infty$.

Nota: estamos hablando de números enteros positivos, por ahora, las definiciones también son válidos cuando se $n$ es real o al $n \to A$ donde $A$ no necesita ser $\infty$, en cuyo caso, hablamos de la desigualdad en la participación en una vecindad de a $A$. Generalmente, lo $A$ es, está claro por el contexto y se queda fuera (otra conveniencia).

Este símbolo se llama BigOh (como parece que sabes ya). Usted puede encontrar más información sobre esto aquí: http://en.wikipedia.org/wiki/Big_O_notation

Así que cuando se utiliza $\mathcal{O}(1/x^2)$, en la expresión

$\ln(1-\frac{1}{x}) = \frac{1}{x} + \mathcal{O}(1/x^2)$ lo que significa realmente es que

para algunos $f \in \mathcal{O}(1/x^2)$ tenemos que

$\ln(1-\frac{1}{x}) = \frac{1}{x} + f(x)$

Ahora usted puede leer Derek respuesta :-) supongo que no tengo que repetir.

Tenga en cuenta que cuando Derek dice

$\ln(1- x) = x + \mathcal{O}(x^2)$, él está hablando acerca de la $x$ en el barrio de $0$.

Hay un montón de otras respuestas aquí que el uso de la BigOh.

Aquí están algunos de ellos (recomiendo especialmente leer la primera)

• La convergencia de $\sqrt{n}x_{n}$ donde $x_{n+1} = \sin(x_{n})$
• Gran $\mathcal{O}$ la Notación de la pregunta, mientras que la estimación de $\sum \frac{\log n}{n}$
• Demostrando $\sum\limits_{p \leq x} \frac{1}{\sqrt{p}} \geq \frac{1}{2}\log{x} -\log{\log{x}}$
• ¿Cuál es la expresión de $n$ que es igual a $\sum_{i=1}^n \frac{1}{i^2}$?