# Series sum is approximately $b\log n$ implies the terms are approximately $b/n$?

Let's say I have a sequence $a_n \ge 0$ such that I know:

$$b \log n - C \le \sum_{i=1}^n a_i \le b \log n + C$$

for some constants $b$ and $C$ larger than 0.

How can I prove that:

$$a_n = \frac{b}{n} + o(1)\ ?$$

This intuitively seems correct because we know that for the harmonic series we get $\sum_{i=1}^n \frac{1}{i} = \log n + o(1)$, but I am not completely sure how to show the reverse.

-
Perhaps $b/n + o(1)$ is not what you intend? Since $b/n$ is, itself, $o(1)$. –  GEdgar Feb 23 '12 at 15:52
@GEdgar: Exactly what I was about to comment! –  Aryabhata Feb 23 '12 at 16:51
I wonder if something along the lines of $a_n=\frac{b}{n}+o(\frac{1}{n})$ can be saved if $a_n$ is required to be nonincreasing? –  Steven Stadnicki Feb 24 '12 at 17:04
Care to accept an answer? –  Did Mar 25 '12 at 22:26

Let $A_n=\sum\limits_{i=1}^na_i$. Call $(*)$ the property that $b\log n-C\leqslant A_n\leqslant b\log n+C$ for every $n\geqslant1$. It is not true that $(*)$ implies that $na_n\to b$.

A first counterexample is $a_{2n}=1/n$ and $a_{2n-1}=0$, for every $n\geqslant1$. Then $(*)$ holds with $b=1$ since $A_n=\log n-\log2+\gamma+o(1)$, but the sequence $(na_n)_n$ diverges since both $0$ and $2$ are limit points.

A second counterexample is $a_n=1$ if $n$ is a power of $k$ and $a_n=0$ otherwise, for some integer $k\geqslant2$. Then $(*)$ holds with $b=1/\log k$ but the sequence $(na_n)_n$ diverges since it is unbounded.

-
Technically, as written, each term of your sequence is indeed $\frac{b}{n} + o(1)$, as $\frac{b}{n}$ is itself $o(1)$. There is a bug in the problem. –  Aryabhata Feb 23 '12 at 16:52
@Aryabatha: I know there is a bug and wrote my answer accordingly. Please read what I wrote. (And technically, as written, your comment does not apply to the second example in my post.) –  Did Feb 23 '12 at 16:54
Sorry, I missed your edit (was commenting on the older version). You have my +1 already. –  Aryabhata Feb 23 '12 at 16:56
So is the statement that harmonic was asking about actually true? And provable (or maybe obvious)? As you say, these counterexamples only apply to your restated problem. –  user12861 Feb 23 '12 at 18:37
@user12861: To be $b/n+o(1)$ for some $b$ is to be $o(1)$. In the second example, $a_n=1$ infinitely many times hence $a_n$ is not $o(1)$. Conclusion: the statement the OP asks to prove is false. –  Did Feb 24 '12 at 6:12

A cleaner version of Didier's example: let $a_n = \frac{1}{n}+(-1)^n$. Then $\displaystyle{\Sigma_{i=1}^n a_i = \log(n)+O(1)}$ but in fact the terms $a_i$ themselves don't even converge, so they're not even $o(1)$, let alone $\frac{1}{ n}+o(\frac{1}{n})$.

-
Steven: Why cleaner? More importantly, the OP asks for some nonnegative $a_n$ and yours are not. Note that shifting your example by $1$ to make every $a_n$ nonnegative yields partial sums which are not $O(\log n)$ anymore. In fact, it seems nonnegative oscillatory counterexamples must be based either on a vanishing amplitude of the oscillations (as in my first case) or on a vanishing frequency (as in my second case). –  Did Feb 24 '12 at 6:24
@DidierPiau My apologies - somehow I missed the nonnegativity in the problem constraint! The 'cleanness' was just based on how much worse we could blow out the constraints on the $a_n$ with a simple individual term, but I agree with you that nonnegative examples where $a_n-b/n$ is larger have to be a bit more complex; your second example is excellent. –  Steven Stadnicki Feb 24 '12 at 17:02