0

Given that sum of $f(n)$ is $f(1)+f(2)+\dots+f(n)$, where $n$ is natural number.

I am stuck with this problem. I tried to use the definition of $\mathcal{O}$, then $$f(1)+f(2)+\cdots+f(n) \le c(g(1)+g(2)+\cdots+g(n))$$ but this seems to be going nowhere. And it seems that I should use $\log$ and the property $\displaystyle\sum_{i=1}^{2^n}\frac{1}{i}\ge \frac{n}{2}.$ Any help, thanks.

an4s
  • 3,716

1 Answers1

0

If you know that the harmonic series is divergent you don't have to use the inequality in the hint. [ You can use it to prove divergence, if you don't know it already]. Let $f(n)=\frac 1 n$ and $g(n)=\frac 1n$. Then $f(n)=\mathcal O (g(n))$ But $f(1)+f(2)+...+f(n)=1+\frac 1 2+...+\frac 1 n$ is no $\mathcal O (ng(n))$ because $f(1)+f(2)+...+f(n) \to \infty$.

Kavi Rama Murthy
  • 311,013
  • Thanks. I did not written very clear in the question, sorry about that. It requires to use the hint. I somehow though it should be disproved by a example involving log(n). –  Mar 13 '18 at 05:57