7
$\begingroup$

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).$

  • 1
    @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.2011-09-09

2 Answers 2

9

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} $

  • 1
    H$u$h. 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.2011-09-09
7

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.)

  • 0
    @robjohn: Right; the terms might cancel. I'll fix it.2011-09-09