How to Use Big O Notation

Question

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:

1. How does Zarrax pass from $\exp(\ln(1 - 3/2n))$ to $\exp(-{3 \over 2n} + O(1/n^2))$?

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

3. How does Zarrax pass from that to $\exp(-{3 \over 2} \ln(n))$?

Thank you for your help.

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

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