"Big-Oh" notation applied to sum

Question

This is the definition of the $\mathcal{O}$ notation in my textbook:

And I need to show the following:

Intuitively, I understand what the proposition tries to say is that because $|f(n)| \leq C . g(n) \, \forall n \geq n_o $, the difference between $C . g(n)$ and$|f(n)|$ for all $n \geq n_o$ will eventually offsets any difference between $f(n)$ and $g(n)$ for $n = 1,2,...,n_o-1$.

But, for example, if $\sum_{k=1}^{n_0-1} f(k) - g(k) > 0$, and $\forall n \geq n_o, |f(n)| = g(n) = 0$, wouldn't we still have $f(n) = \mathcal{O}(g(n))$, but there wouldn't be any $n_o'$ and $C'$ such that $\forall n \geq n_o'$, $\sum_{k=1}^{n}| f(k)| \leq C'.\sum_{k=1}^{n} g(k)$?

Answer 1

From definition,$$\sum_{k=1}^{n}f(k)=O\left(\sum_{k=1}^{n}g(k)\right)$$ means there exists constant $n_0$ and $C$ such that for any $n\geq n_0$, $$\left|\sum_{k=1}^{n}f(k)\right|\leq C\sum_{k=1}^{n}g(k).$$

So suppose $f(n)=O(g(n))$. We have $$\begin{align*}\left|\sum_{k=1}^{n}f(k)\right|&\leq\sum_{k=1}^{n}\left|f(k)\right|\qquad \text{Triangle inequality} \\ &=\sum_{k=1}^{n_0-1}\left|f(k)\right|+\sum_{k=n_0}^{n}\left|f(k)\right|\\ &\leq\color{blue}{\sum_{k=1}^{n_0-1}\left|f(k)\right|}+C\sum_{k=n_0}^{n}g(k)\\ &\stackrel{?}{\leq}\color{green}{C\sum_{k=1}^{n_0-1}g(k)}+C\sum_{k=n_0}^{n}g(k)\\ &=C\sum_{k=1}^{n}g(k) \end{align*}$$

Your intuition is correct, but the example you gave doesn't fit some assumptions, i.e. $g(n)\ne0$ for a large $n$ (as enedil pointed out). In fact, for $n$ being large, the inequality holds, since the blue term will be a constant, and that the green one is also a constant as $n$ goes to $+\infty$. So in terms of asymptotic analysis, the theorem is true.

Answer 2

Yes, with this definition e.g.

$$f(k)=\begin{cases}1\text{ if }k=1\\ 0\text{ otherwise}\end{cases}$$ and $g(k)\equiv 0$ is a counterexample to the "fact".

Even modifying the definition of $O(\cdot)$ to say that $f(n)=O(g(n))$ if there are $n_0,C$ such that $g(n)\neq 0$ and $|f(n)|\leq Cg(n)$ for $n\geq n_0$ is not enough, since then you have a different type of counterexample using the same $f$ and $g(n)=(-1)^n$. Here $f(n)=O(g(n))$ by the new definition (with $C=0$), but $\sum_1^n f(k)$ and $\sum_1^n g(k)$ do not satisfy the new definition, since $\sum_1^n g(k)=0$ infinitely often.

What you need to add to the definition (which is fairly standard, e.g. see the Wikipedia article on big O) is the requirement that $g(n)>0$ for $n$ sufficiently large.