6

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.

Aryabhata
  • 82,206
harmonic
  • 127

2 Answers2

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.

Did
  • 279,727
  • 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 06:12
  • 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). – user12861 Feb 24 '12 at 15:41
  • 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.) – Did Feb 24 '12 at 16:28
  • @user12861: In addition to what Didier says, please check out the difference between BigOh and SmallOh.I am guessing you are conflating the two. – Aryabhata Feb 24 '12 at 16:55
  • Thanks for the explanation. You're right, I just wasn't familiar with SmallOh notation. – user12861 Feb 25 '12 at 03:53
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})$.

Steven Stadnicki
  • 51,746
  • 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). – Did Feb 24 '12 at 06: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