31
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ It's certainly true if $f(n) \to \infty$. $\endgroup$ – Antonio Vargas Mar 3 '12 at 2:51
23
$\begingroup$

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

$\endgroup$
  • $\begingroup$ +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 :-) $\endgroup$ – Aryabhata Mar 3 '12 at 3:25
  • $\begingroup$ @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! $\endgroup$ – Antonio Vargas Mar 3 '12 at 3:28
  • $\begingroup$ @Aryabhata: I have added another case in my post. $\endgroup$ – Antonio Vargas Mar 3 '12 at 6:43
  • $\begingroup$ 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." $\endgroup$ – Antonio Vargas Mar 3 '12 at 16:00
  • $\begingroup$ I don't think you should worry about bumping. Not all people read the comments, so it might be better to have it in the answer. $\endgroup$ – Aryabhata Mar 5 '12 at 1:03
8
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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