Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
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. –  Mike Spivey Sep 9 '11 at 4:13

2 Answers 2

up vote 8 down vote accepted

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

share|improve this answer
1  
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.)

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.