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.

  • 4
    Perhaps $b/n + o(1)$ is not what you intend? Since $b/n$ is, itself, $o(1)$.2012-02-23
  • 0
    @GEdgar: Exactly what I was about to comment!2012-02-23
  • 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
    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.2012-02-23
  • 0
    @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.)2012-02-23
  • 0
    Sorry, I missed your edit (was commenting on the older version). You have my +1 already.2012-02-23
  • 0
    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.2012-02-23
  • 0
    @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.2012-02-24
  • 0
    I understand that b/n + o(1) is o(1). I'm confused as to why 1 is not o(1). It doesn't matter if it happens infinitely many times (in the original problem description).2012-02-24
  • 0
    user12861: To be $o(1)$ is to converge to zero. A sequence whose infinitely many terms are $1$ does not converge to zero. (May I suggest you check again the definition of the [limit of a sequence](http://en.wikipedia.org/wiki/Limit_of_a_sequence).)2012-02-24
  • 0
    @user12861: In addition to what Didier says, please check out the difference between BigOh and SmallOh.I am guessing you are conflating the two.2012-02-24
  • 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})$.

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