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.

Recently I came across the nice result that

$$\left\lfloor n \right\rfloor - \left\lfloor\frac{n}{2}\right\rfloor + \left\lfloor\frac{n}{3}\right\rfloor - \left\lfloor \frac{n}{4}\right\rfloor + \dots \sim n \log 2$$

where $\displaystyle a_n \sim b_n$ means $\displaystyle \lim_{n\to \infty} \frac{a_n}{b_n} = 1$.

So basically, what the above result says is that

$$\left\lfloor n \right\rfloor - \left\lfloor\frac{n}{2}\right\rfloor + \left\lfloor\frac{n}{3}\right\rfloor - \left\lfloor \frac{n}{4}\right\rfloor + \dots + (-1)^n\left\lfloor \frac{n}{n}\right\rfloor \sim n - \frac{n}{2} + \frac{n}{3} - \frac{n}{4} + \dots + (-1)^n\frac{n}{n}$$

and the fact that we take the integer part has no effect, asymptotically.

So I tried a few other sequences, like the harmonic series, and geometric series with ratio $\frac{1}{2}$, and the results seemed to be similar, but the proofs were dependent on the series in question.

So trying to generalize:

Suppose $a_1, a_2, \dots, a_n, \dots$ is a sequence of non-zero integers, such that $|a_1| \lt |a_2| \lt \dots \lt |a_n| \lt \dots$ and

$$ \sum_{k=1}^{n} \frac{1}{a_k} \sim f(n)$$

(Note that $f(n)$ can be constant).

Let $s_i$ be the sign of $a_i$ (i.e. $s_i = 1$ if $a_i \gt 0$, and $-1$ otherwise).

The question is, is it true that

$$ \sum_{k=1}^{n} s_i \left\lfloor \frac{n}{|a_k|}\right\rfloor \sim n f(n)$$

?

I hope it isn't something obvious...

share|improve this question
    
What happens if we take $a_i \approx 1/(n+1)$ for each $i$? Then it seems that $f(n) \approx 1$ and your second sum becomes $0$. But maybe I'm missing something. –  TMM Mar 3 '12 at 0:56
    
@TMM: $a_i$ are distinct integers. –  Aryabhata Mar 3 '12 at 0:57
    
Ah, so I was missing something... Anyway interesting question! –  TMM Mar 3 '12 at 1:03
    
@TMM: Thanks..! –  Aryabhata Mar 3 '12 at 1:16
1  
It's certainly true if $f(n) \to \infty$. –  Antonio Vargas Mar 3 '12 at 2:51

2 Answers 2

Let $(a_n)$ be a sequence of real numbers.

Here is the proof for the case $|f(n)| \to \infty$.

Write $$\left\lfloor \frac{n}{|a_k|}\right\rfloor = \frac{n}{|a_k|} - \delta_{k,n},$$

where $0 \leq \delta_{k,n} < 1$. Substituting this into the sum we get

$$\begin{align*} \sum_{k=1}^{n} s_k \left\lfloor \frac{n}{|a_k|}\right\rfloor &= \sum_{k=1}^{n} \left(\frac{n}{a_k} - s_k \delta_{k,n}\right) \\ &= n \sum_{k=1}^{n}\frac{1}{a_k} - \sum_{k=1}^{n} s_k \delta_{k,n}. \end{align*}$$

We can get a crude bound on the right sum,

$$\left|\sum_{k=1}^{n} s_k \delta_{k,n}\right| \leq \sum_{k=1}^{n} \delta_{k,n} < n,$$

so that

$$\sum_{k=1}^{n} s_k \left\lfloor \frac{n}{|a_k|}\right\rfloor = n \sum_{k=1}^{n}\frac{1}{a_k} + O(n).$$

Thus

$$\frac{\sum_{k=1}^{n} s_k \left\lfloor \frac{n}{|a_k|}\right\rfloor}{n f(n)} = \frac{\sum_{k=1}^{n} \frac{1}{a_k}}{f(n)} + O\left(\frac{1}{f(n)}\right) \to 1.$$

Q.E.D.


Edit: Here is the proof of another case. Define $M(n)$ to be the least integer, if it exists, such that $n < |a_k|$ for all $k > M(n)$.

Proposition. Suppose that

  1. $0 < C \leq |f(n)|$ for $n$ large enough,

  2. $n/a_n = o(1)$,

  3. $M(n) = o(n)$,

  4. $f(n) \sim b\,f(M(n))$ for some constant $b$.

Then $$\sum_{k=1}^{n} s_k \left\lfloor \frac{n}{|a_k|}\right\rfloor \sim n f(n).$$

Note that since $n/a_n \to 0$, $M(n)$ exists and $M(n) \to \infty$.

Proof. We define $\delta_{k,n}$ as above. The sum becomes

$$\sum_{k=1}^{n} s_k \left\lfloor \frac{n}{|a_k|}\right\rfloor = n \sum_{k=1}^{M(n)}\frac{1}{a_k} - \sum_{k=1}^{M(n)} s_k \delta_{k,n}.$$

We again get a rough bound on the right sum,

$$\left|\sum_{k=1}^{M(n)} s_k \delta_{k,n}\right| < M(n),$$

and so

$$\frac{\sum_{k=1}^{n} s_k \left\lfloor \frac{n}{|a_k|}\right\rfloor}{b n f(M(n))} = \frac{\sum_{k=1}^{M(n)} \frac{1}{a_k}}{b f(M(n))} + O\left(\frac{M(n)}{n}\right) \to 1.$$

Thus $$\sum_{k=1}^{n} s_k \left\lfloor \frac{n}{|a_k|}\right\rfloor \sim b n f(M(n)) \sim n f(n).$$

Q.E.D.

Corollary. Suppose that

  1. $a_n > 0$ for all $n$,

  2. $\sum 1/a_n < \infty$,

  3. $M(n) = o(n)$.

Then $$\sum_{k=1}^{n} \left\lfloor \frac{n}{a_k}\right\rfloor \sim n f(n).$$

We will write "$n$C" to refer to condition $n$ in the corollary, and "$n$P" to refer to condition $n$ in the proposition.

Proof. Conditions 1C and 2C imply 2P immediately. Further, we can write $$f(n) = \sum_{k=1}^{\infty} \frac{1}{a_k} + o(1),$$ which implies conditions 1P and 4P.

Q.E.D.

As an application of the above corollary, all $p$-series have the desired property. We appeal to the proposition to see that all real geometric series (except $\sum (-1)^n$) also have the desired property. The result is then true for all series which do not converge to $0$ whose convergence may be deduced by comparison with a $p$-series or a geometric series.


Edit 2: I just wanted to add to this that there is an interesting result by H. Shapiro which can be thought of as a partial converse to the idea we're discussing here. The result is proved and subsequently used to derive a result on the order of the prime counting function in this paper.

I state only the relevant part here.

Proposition (Shapiro). Let $(a_n)$ be a nonnegative sequence such that $$\sum_{k=1}^{n} a_n \left\lfloor\frac{n}{k}\right\rfloor = n \log n + O(n)$$ for all $n \geq 1$. Then $$\sum_{k=1}^{n} \frac{a_k}{k} = \log n + O(1).$$

share|improve this answer
    
+1: Thanks for this. This was the reason I made sure to mention $f(n)$ can be constant. Of course, I had only looked at the case $a_i \gt 0$, so this is nice :-) –  Aryabhata Mar 3 '12 at 3:25
    
@Aryabhata: I'm working on the general case, but I hope someone will beat me to it because I'm very interested to know the answer too! –  Antonio Vargas Mar 3 '12 at 3:28
    
@Aryabhata: I have added another case in my post. –  Antonio Vargas Mar 3 '12 at 6:43
    
Thank you......! –  Aryabhata Mar 3 '12 at 6:51
    
To avoid bumping the post: The last line should be "The result is then true for all series which do not converge to $0$ whose convergence may be deduced by comparison with a p-series or a geometric series." –  Antonio Vargas Mar 3 '12 at 16:00

Here is a different way to look at the proof for when $f(n)\rightarrow \infty$. We can apply the same approach as done in this answer; since $\lfloor x\rfloor =x+O(1)$, we have that $$\sum_{k=1}^n s_k \left\lfloor \frac{n}{|a_k|}\right\rfloor = n\sum_{k=1}^n \frac{s_k}{|a_k|}+O(n)=nf(n)+O(n).$$

Hence, if $f(n)\rightarrow \infty$, we have the desired asymptotic.

Alternating series:

In the case where $a_k$ is an alternating series, we can prove the theorem by using the hyperbola method, exploiting the fact that the series alternates.
Let $b_{k}=|a_{k}|.$ Then $0<b_{1}<b_{2}<\cdots<b_{k}$ so that $b_{k}\geq k,$ and $b_k=(-1)^ka_k$. Then

$$\sum_{k\leq n}s_{k}\left[\frac{n}{|a_{k}|}\right]=\sum_{k\leq n}(-1)^{k}\sum_{d\leq n,\ b_{k}|d}1=\sum_{d\leq n}\sum_{\begin{array}{c} k\leq n\\ b_{k}|d \end{array}}(-1)^{k}.$$ This is then

$$\sum_{\begin{array}{c} db_{k}\leq n\\ k\leq n \end{array}}(-1)^{k}=\sum_{db_{k}\leq n}(-1)^{k}$$ where we may remove the additional condition on $k$ since $k\leq b_{k}.$ Let $A>0.$ By examining the areas of various parts of the hyperbola $xy=n,$ we may split the above as $$\sum_{d\leq A}\sum_{b_{k}\leq\frac{n}{d}}(-1)^{k}+\sum_{b_{k}\leq\frac{n}{A}}\sum_{d\leq\frac{n}{b_{k}}}(-1)^{k}-\sum_{d\leq A}\sum_{b_{k}\leq\frac{n}{A}}(-1)^{k}.$$ Since $\sum_{b_{k}\leq x}(-1)^{k}=O(1),$ we see that the above is $$\sum_{b_{k}\leq\frac{n}{A}}\sum_{d\leq\frac{n}{b_{k}}}(-1)^{k}+O(A)=\sum_{b_{k}\leq\frac{n}{A}}(-1)^{k}\left[\frac{n}{b_{k}}\right]+O(A) =n\sum_{b_{k}\leq\frac{n}{A}}\frac{1}{a_{k}}+O\left(A+\frac{n}{A}\right)$$ and taking $A=\sqrt{n}$ this is

$$=n\sum_{b_{k}\leq\sqrt{n}}\frac{1}{a_{k}}+O\left(\sqrt{n}\right).$$ We may extend the above sum into $\sum_{k\leq n}\frac{1}{a_{k}}$ introducing an error term of the form $o(1)$, (which when multiplying by $n$ is $o(n)$) since the series $\sum_{k}\frac{1}{a_{k}}$ converges by the alternating series test. This then implies that $$n\sum_{k\leq n}\frac{1}{a_k}\sim \sum_{k\leq n}s_k \left\lfloor \frac{n}{|a_k|}\right\rfloor.$$

share|improve this answer
    
You should explicitly state that $k \leq b_k$ is an assumption. You do not treat $a_k = (-1)^k \log k$, for example. –  Antonio Vargas Mar 5 '12 at 21:08
1  
@AntonioVargas: I did state exactly that. In the question he has that the $|a_k|$ are integers, and $|a_k|\leq |a_{k+1}|$, so we must have $b_k\geq k$. I knew this wasn't that clear, so when I wrote this answer I added in the additional line "Then $0<b_{1}<b_{2}<\cdots<b_{k}$ so that $b_{k}\geq k...$" –  Eric Naslund Mar 5 '12 at 21:25
    
Ah, I completely missed that from the original question! Silly of me. –  Antonio Vargas Mar 5 '12 at 21:34

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.