6
$\begingroup$

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.

  • 1
    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?2012-02-24

2 Answers 2

4

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.

  • 0
    Thanks for the explanation. You're right, I just wasn't familiar with SmallOh notation.2012-02-25
3

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

  • 0
    @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.2012-02-24