How to Use Big O Notation
In my question about the convergence/divergence of
$$ \sum_{n=2}^\infty \frac{1\cdot 3\cdot 5\cdot 7\cdots (2n-3)}{2^nn!}. $$
here: Why Doesn't This Series Converge?
Zarrax gave the answer:
"You can use Taylor approximations here. Note that the ratio between consecutive terms is ${2n - 3 \over 2n} = \exp(\ln(1 - 3/2n)) = \exp(-{3 \over 2n} + O(1/n^2))$. So the product is comparable to $\exp(-{3 \over 2} \sum_{i = 2}^n {1 \over n} + O(1/n))$, which in turn is comparable to $\exp(-{3 \over 2} \ln(n))$ or $n^{-{3 \over 2}}$. Thus the series converges."
I've decided to give a talk in a graduate seminar about the danger of coming up with examples off the top of your head and now wish to understand what this answer means. The problem is that I have no exposure to big O notation and am not having luck online. Basically, I don't understand the answer at all. I can break it into a few questions:
How does Zarrax pass from $\exp(\ln(1 - 3/2n))$ to $\exp(-{3 \over 2n} + O(1/n^2))$?
To which product is Zarrax referring in his third sentence? And how is it comparable to $\exp(-{3 \over 2} \sum_{i = 2}^n {1 \over n} + O(1/n))$?
How does Zarrax pass from that to $\exp(-{3 \over 2} \ln(n))$?
Thank you for your help.
Solution 1:
To answer your questions:
1) He is using $\log(1-x) = -x-x^2/2-x^3/3 - \cdots = -x + O(x^2).$
2) The product he's referring to is $$\frac{1\cdot 3\cdot 5\cdot 7\cdots (2n-3)}{2^nn!}$$
and it's comparable to $\exp(-{3 \over 2} \sum_{i = 2}^n {1 \over n} + O(1/n))$ because this is the product of $n-1$ versions of $\exp(-{3 \over 2n} + O(1/n^2)).$
3) He uses $\sum_{i=2}^n 1/i = \log n + \text{constant} + O(1/n).$
Solution 2:
When an expression uses $\mathcal{O}(1/n^2)$ it means that this is actually a function $f$ such that $f \in \mathcal{O}(1/n^2)$. This is a very convenient abuse of notation.
Note that $\mathcal{O}(1/n^2)$ is actually a set of functions. A function $f \in \mathcal{O}(1/n^2)$ iff there is a constant $C$ (dependent on $f$) such that $|f(n)| \le \frac{C}{n^2}$ for all sufficiently large $n$, i.e. as $n \to \infty$.
Note: we are talking about positive integers for now, the definitions are also valid when $n$ is real or when $n \to A$, where $A$ need not be $\infty$, in which case, we talk about the inequality holding in a neighbourhood of $A$. Usually, what $A$ is, is clear from the context and is left out (another convenience).
This symbol is called BigOh (as you seem to know already). You can find more information about that here: http://en.wikipedia.org/wiki/Big_O_notation
So when you use $\mathcal{O}(1/x^2)$, in the expression
$\ln(1-\frac{1}{x}) = \frac{1}{x} + \mathcal{O}(1/x^2)$ what we really mean is that
for some $f \in \mathcal{O}(1/x^2)$ we have that
$\ln(1-\frac{1}{x}) = \frac{1}{x} + f(x)$
Now you can read Derek's answer :-) I guess I don't have to repeat it.
Note that when Derek says
$\ln(1- x) = x + \mathcal{O}(x^2)$, he is talking about $x$ in the neigbourhood of $0$.
There are plenty of other answers here which use the BigOh.
Here are a few of them (I especially recommend you read the first one)
- Convergence of $\sqrt{n}x_{n}$ where $x_{n+1} = \sin(x_{n})$
- Big $\mathcal{O}$ Notation question while estimating $\sum \frac{\log n}{n}$
- Proving $\sum\limits_{p \leq x} \frac{1}{\sqrt{p}} \geq \frac{1}{2}\log{x} -\log{\log{x}}$
- What is the expression of $n$ that equals to $\sum_{i=1}^n \frac{1}{i^2}$?