Rounding is asymptotically useless?

Question

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 the following true?

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

_{I hope it isn't something obvious...}

Answer 1

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

Answer 2

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