Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
4  
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
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? –  Steven Stadnicki Feb 24 '12 at 17:04
    
Care to accept an answer? –  Did Mar 25 '12 at 22:26

2 Answers 2

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.

share|improve this answer
    
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})$.

share|improve this answer
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 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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.