Closed form for estimated sum with different asymptotic bounds?

88 Views Asked by At

I found asymptotic lower and upper bounds for a summation as follows:

$$ 1 - O\left(\frac{\log_2^2 n}{n}\right) \le \sum_{k=1}^n f(k) \le 1 + O\left(\frac{1}{n}\right).$$

If you want to write it in a closed form, how would you write it? Can you say: $\sum_{k=1}^n f(k) = 1 + O\left(\frac{1}{n}\right)$?

Thank you.

1

There are 1 best solutions below

0
On BEST ANSWER

I think there is some ambiguity in your formulation.

If, for appropriate $f$, as $N \rightarrow +\infty$, we have $$ \sum_{n=n_0}^{N} f(n) = 1 + O\left(\frac{1}{N}\right) \tag1$$ then $$ \sum_{n=n_0}^{N} f(n) = 1 + O\left(\frac{\log_2^2 N}{N}\right) \tag2$$ that's what can be said in general.

The converse implication: $(1) \Leftarrow (2)$ is false.

A counter-example: We have $$ \frac{\log_2 N}{N}=O\left(\frac{\log_2^2 N}{N}\right) $$ but $$ \log_2 N = \frac{\frac{\log_2 N}{N}}{\frac{1}{N}} \longrightarrow +\infty $$ and $$ \frac{\log_2 N}{N}\neq O \left(\frac{1}{N}\right) $$ as $N \rightarrow +\infty$.