# Problem from the Cormen appendix C 1.13

I am currently working on CLRS 1.13. The idea is to use Stirling's approximation to prove that

$${2n \choose n} = \frac{2^{2n}}{\sqrt{\pi n}} \left( 1 + O \left( \frac{1}{n} \right) \right)$$

Now directly replacing Stirling's approximation I arrive to something like:

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

Now the quotient is a function that ends up being $$O(\frac{1}{n})$$ because we have terms in $$O(\frac{1}{n})$$ and $$O(\frac{1}{2n})$$. The problem is that even if there is a quotient of two functions that are $$O(\frac{1}{n})$$.

I don't know if the result is still $$O(\frac{1}{n})$$. In fact I haven't seen any general rule for the quotient of two big $$O$$ s.

Is there a general rule that I can apply here?

## 1 Answer

Just simply use the inequality $$1 + \Theta(1/n) \geq 1$$ in the denominator. You will get the required answer.

• @plop $f(n)$ is positive right? so the inequality should be correct for all $f \in \Theta(1/n)$. – Inuyasha Yagami Feb 1 at 16:59
• I was wrong. I was reading $\Theta$ and thinking $O$. For $n$ large, the elements of $\Theta$ do become positive. – plop Feb 1 at 17:02
• @plop I am not aware of the definition of $\Omega$ or $O$ for negative functions. :p – Inuyasha Yagami Feb 1 at 18:09
• @plop However, in Stirling's approximation, the function $f$ is indeed positive. – Inuyasha Yagami Feb 1 at 18:10
• It is the same definitions. They don't make any assumption about the sign of the function. In the case of $\Theta(1/n)$ it follows as a consequence of the definition, since $f\in\Theta(1/n)$ must satisfy $K_1/n\leq f(n)\leq K_2/n$ for some $K_1,K_2>0$ and sufficiently large $n$. – plop Feb 1 at 18:36