¿Es correcta esta ecuación asintótica?

Question

¿Es correcta esta ecuación?

$$ \frac {1 + \Theta(\frac 1 {2n})} {(1 + \Theta(1/n))^2} = 1 + O(1 / n) $$

Necesito esta ecuación para comprobar

$$ \binom {2n} n = \frac {2 ^ {2n}} {\sqrt {\pi n}} (1 + O(1 / n)) $$

que podría ser calculado de la aproximación de Stirling:

$$ n! = \sqrt {2\pi n} \left(\frac n e\right)^n \left(1 + \Theta({\frac 1 n})\right).$$

Answer 1

Supongamos que $Bx\le\Theta(x)\le Cx$ cada $\Theta$.

$$ \begin{align} \frac{1+\Theta(\frac{1}{2n})}{(1+\Theta(\frac{1}{n}))^2} &\le\frac{1+\frac{C}{2n}}{(1+\frac{B}{n})^2}\\ &=(1+\frac{C}{2n})(1-2\frac{B}{n}+O(\frac{1}{n^2}))\\ &=(1+(\frac{C}{2}-2B)\frac{1}{n}+O(\frac{1}{n^2}))\\ &=1+O(\frac{1}{n}) \end {Alinee el} $$ $$ \begin{align} \frac{1+\Theta(\frac{1}{2n})}{(1+\Theta(\frac{1}{n}))^2} &\ge\frac{1+\frac{B}{2n}}{(1+\frac{C}{n})^2}\\ &=(1+\frac{B}{2n})(1-2\frac{C}{n}+O(\frac{1}{n^2}))\\ &=(1+(\frac{B}{2}-2C)\frac{1}{n}+O(\frac{1}{n^2}))\\ &=1+O(\frac{1}{n}) \end {Alinee el} $$

Answer 2

Sí. Una forma de verlo es hacer la división larga; es decir, dividir el denominador en el numerador. El numerador es $1 + \Theta(\frac{1}{2n}) = 1 + \Theta(\frac{1}{n})$, y el denominador es $\left(1 + \Theta(\frac{1}{n})\right)^2 = 1 + \Theta(\frac{1}{n}) + \Theta(\frac{1}{n^2}) = 1 + \Theta(\frac{1}{n})$. No voy a tratar de componer la división larga en este foro, pero intenta y verás que consigues $1$con un resto de % de $O(\frac{1}{n})$. Por lo que tiene

%#% $ #% puesto que el denominador es $$\frac {1 + \Theta(\frac{1}{2n})} {\left(1 + \Theta(\frac{1}{n})\right)^2} = \frac{1 + \Theta(\frac{1}{n})}{1 + \Theta(\frac{1}{n})} = 1 + \frac{O(\frac{1}{n})}{1 + \Theta(\frac{1}{n})} = 1 + O\left(\frac{1}{n}\right),$.

(Recuerde que $O(1)$, ya que el constante $\Theta(\frac{1}{2n}) = \Theta(\frac{1}{n})$ no afecta el orden asintótico).