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.


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


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)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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