# Is this asymptotic equation correct?

Is this equation correct?

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

I need this equation to prove that

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

which could be calculated from Stirling's Approximation:

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

-
It is correct. Both the numerator and the denominator are $1+O(1/n)$. So the ratio is also $1+O(1/n)$. –  Srivatsan Sep 9 '11 at 2:27
Can you give a more formal proof? Intuitively it's correct, but I always want to know how to do this kind of asymptotic calculation formally. –  ablmf Sep 9 '11 at 2:32
@ablmf: did you mean $1+\Theta(1/(2n))$ in the numerator? –  robjohn Sep 9 '11 at 2:43
What is the $\Theta$ used for? Is it meant to be the big-O notation? I never saw it before. –  Patrick Da Silva Sep 9 '11 at 3:39
@Patrick: A function is $\Theta(f(n))$ if its asymptotic growth is exactly on the order of $f(n)$. A function is $O(f(n))$ if its asymptotic growth is no larger than $f(n)$. Some people use the latter to mean the former, which sometimes causes confusion. –  Mike Spivey Sep 9 '11 at 4:13

Suppose $Bx\le\Theta(x)\le Cx$ for each $\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{align} \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{align}

-
Huh. Over an hour, and no upvotes on either of our answers. Well, +1 from me, because it's useful to see how to do this from the definition, too. –  Mike Spivey Sep 9 '11 at 4:12

Yes. One way to see it is to do the long division; i.e., divide the denominator directly into the numerator. The numerator is $1 + \Theta(\frac{1}{2n}) = 1 + \Theta(\frac{1}{n})$, and the denominator is $\left(1 + \Theta(\frac{1}{n})\right)^2 = 1 + \Theta(\frac{1}{n}) + \Theta(\frac{1}{n^2}) = 1 + \Theta(\frac{1}{n})$. I'm not going to attempt to typeset the long division on this forum, but try it, and you'll see that you get $1$ with a remainder of $O(\frac{1}{n})$. So you have

$$\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),$$ since the denominator is $O(1)$.

(Remember that $\Theta(\frac{1}{2n}) = \Theta(\frac{1}{n})$, since the constant $\frac{1}{2}$ doesn't affect the asymptotic order.)

-
I don't think you can bound the ratio away from $1$, so I don't think you can say $1+\Theta(1/n)$. –  robjohn Sep 9 '11 at 2:54
@robjohn: Right; the terms might cancel. I'll fix it. –  Mike Spivey Sep 9 '11 at 2:59