$\lim_{n\to\infty}\frac{n -\big\lfloor\frac{n}{2}\big\rfloor+\big\lfloor\frac{n}{3}\big\rfloor-\dots}{n}$, a Brilliant problem

Question

I encounter a question when visiting Brilliant:

Find

$\space\space\space\space\lim_{n\to\infty}s_n$

$=\lim_{n\to\infty}\frac{n - \big \lfloor \frac{n}{2} \big \rfloor+ \big \lfloor \frac{n}{3} \big \rfloor - \big \lfloor \frac{n}{4} \big \rfloor + \dots}{n}$

$=\lim_{n\to\infty}\frac{\sum_{k=1}^n(-1)^{k+1}\lfloor\frac{n}{k}\rfloor}{n}$

The answer in the website above doesn't really satisfies me, as the answer does not tell how the sequence converge and I doesn't understand how we can take subsequence $n_k=k!$ to solve the problem.

I had some idea but doesn't seems to work:

1) It is easy to show $$s_n=\frac{\sum_{k=1}^{\big\lceil\frac{n}{2}\big\rceil}(\big\lfloor\frac{n}{2k-1}\big\rfloor-\big\lfloor\frac{n}{2k}\big\rfloor)}{n}$$

2) On the other hand,

$$s_n\approx\sum_{k=1}^n(-1)^{k+1}\frac{1}{k}\to\ln2$$

So I am wondering how $s_n\approx$ the alternate hamonic series $$\forall(n,k\in\mathbb N:n\ge k),\space\space\frac{n}{k}\in\Bigg[\bigg\lfloor\frac{n}{k}\bigg\rfloor,\bigg\lfloor\frac{n}{k}\bigg\rfloor+\bigg(\frac{k-1}{k}\bigg)\Bigg]$$

I tried to look at the graph, the sequence $s_n$ is very likely to converge to $\ln 2$, and the alternating harmonic series seems to be bounded by the graph of $s_n$ at most of the time.

3) Also I observed that $s_8=\frac{8-4+2-2+1-1+1-1}{8}=\frac{1}{2}$, the terms cancelled nicely, but I am afraid that the anlalogue is not generaly true for all $s_{2^k}$.

4) I have tried to use Stolz–Cesàro Theorem, but doesn't seems useful neither.

5) I know that $\forall x,y\in\mathbb R:x+y\in\mathbb Z, \lfloor x\rfloor+\lceil y\rceil=x+y$, which maybe is useful since we may thus write $s_n$ in a more beautiful manner?

6) If there is no $(-1)^{k+1}$, I think we can treat $s_n$ as a Riemann sum, but well, ... , seems useless.

7) I have tried to think about how many terms of summand of $ns_n$ is integer.

8) I have tried to think $\big\lfloor\frac{n}{k}\big\rfloor$ as the number of positive integer multiple of $k$ that $\lt n$, and I then considered sets of number that is counted and uncounted respectively, but well, the question doesn't seems that easy.

Does this help? (1) (2) (3)

Any help will be appreciate. Thank you!

Remarks: I was wondering is there a deep subject studying this (if so references please). Can this (or variants) be represented as a simpler function?

Answer 1

Let $f : [0, 1] \to \mathbb{R}$ be defined by

$$f(x) = \mathbf{1}_{\{\text{$x > 0$ and $\lfloor 1/x \rfloor$ is odd}\}} = \sum_{i=1}^{\infty} \mathbf{1}_{\{ 2i-1 \leq \frac{1}{x} < 2i \}}. $$

Then by double counting, we find that

\begin{align*} s_n = \sum_{k=1}^{n} (-1)^{k-1} \bigg\lfloor \frac{n}{k} \bigg\rfloor &= \sum_{k=1}^{n} (-1)^{k-1} \sum_{j=1}^{n} \mathbf{1}_{\{kj \leq n\}} \\ &= \sum_{j=1}^{n} \sum_{k=1}^{n} (-1)^{k-1} \mathbf{1}_{\{kj \leq n\}} = \sum_{j=1}^{n} f\left(\frac{j}{n}\right). \end{align*}

Now we utilize the following lemma:

Lemma. Let $f : [0, 1] \to \mathbb{R}$ be Riemann integrable. Then $$ \lim_{n\to\infty} \sum_{j=1}^{n} f\left(\frac{j}{n}\right)\frac{1}{n} = \int_{0}^{1} f(x) \, dx. $$

From this, we know that $s_n/n$ converges and

$$ \lim_{n\to\infty} \frac{s_n}{n} = \int_{0}^{1} f(x) \, dx = \sum_{i=1}^{\infty} \left( \frac{1}{2i-1} - \frac{1}{2i} \right) = \log 2. $$

Answer 2

Note that $$\frac{1}{n}\sum_{k=1}^{n}(-1)^{k+1}\left\lfloor\frac{n}{k}\right\rfloor=\frac{1}{n}\sum_{k=1}^{n}\left\lfloor\frac{n}{k}\right\rfloor-\frac{1}{n/2}\sum_{k=1}^{\lfloor n/2\rfloor}\left\lfloor\frac{n/2}{k}\right\rfloor=\frac{D(n)}{n}-\frac{D(n/2)}{n/2}.$$ where $D(x)= \sum_{k\geq 1}^{n}\left\lfloor\frac{x}{k}\right\rfloor$ is the divisor summatory function. It is known that $$D(x) = x\ln(x) + x(2\gamma -1) + O(\sqrt{x})\implies \frac{D(x)}{x} = \ln(x) + (2\gamma -1) + o(1)$$ (see also Dirichlet's Divisor Problem). Hence, as $n$ goes to $+\infty$, $$\frac{1}{n}\sum_{k=1}^{n}(-1)^{k+1}\left\lfloor\frac{n}{k}\right\rfloor= \ln(n)-\ln(n/2)+o(1)\to \ln(2).$$

Answer 3

Elementary high school approach

One can show immediately with the squeeze theorem that $$L_1=\lim_{n\to\infty}\left(\sum_{k=1}^{2\left\lfloor \sqrt{n} \right\rfloor}\frac{1}{2n}\left\lfloor\frac{2n}{k}\right\rfloor-\sum_{k=1}^{\left\lfloor \sqrt{n} \right\rfloor}\frac{1}{n}\left\lfloor\frac{n}{k}\right\rfloor\right)=\log(2),$$

using the simple fact that $\lim_{n\to\infty}(H_{2n}-H_n)=\log(2)$.

But guess what! Your limit is

$$\lim_{n\to\infty}\left(\sum_{k=1}^{2n}\frac{1}{2n}\left\lfloor\frac{2n}{k}\right\rfloor-\sum_{k=1}^{n}\frac{1}{n}\left\lfloor\frac{n}{k}\right\rfloor\right)=L_1,$$ and therefore you can use the first limit to calculate your initial limit and then show that the sum of the remaining terms tends to $0$, which is straightforward.

Adding some steps requested by OP

WLOG, for the comfort of calculations, we can replace in the initial limit $n$ by $2n$, and using the double inequality with floor function $x\ge\left\lfloor x\right\rfloor\ge x-1$, we have

$$H_{2\left\lfloor\sqrt{n}\right\rfloor}\ge\sum_{k=1}^{2\left\lfloor\sqrt{n}\right\rfloor}\frac{1}{2n}\left\lfloor\frac{2n}{k}\right\rfloor\ge H_{2\left\lfloor\sqrt{n}\right\rfloor}-\frac{\left\lfloor\sqrt{n}\right\rfloor}{n}$$

$$-H_{\left\lfloor\sqrt{n}\right\rfloor}+\frac{\left\lfloor\sqrt{n}\right\rfloor}{n}\ge-\sum_{k=1}^{\left\lfloor\sqrt{n}\right\rfloor}\frac{1}{n}\left\lfloor\frac{n}{k}\right\rfloor\ge-H_{\left\lfloor\sqrt{n}\right\rfloor},$$ that give $$H_{2\left\lfloor\sqrt{n}\right\rfloor}-H_{\left\lfloor\sqrt{n}\right\rfloor}+\frac{\left\lfloor\sqrt{n}\right\rfloor}{n}\ge\sum_{k=1}^{2\left\lfloor\sqrt{n}\right\rfloor}\frac{1}{2n}\left\lfloor\frac{2n}{k}\right\rfloor-\sum_{k=1}^{\left\lfloor\sqrt{n}\right\rfloor}\frac{1}{n}\left\lfloor\frac{n}{k}\right\rfloor\ge H_{2\left\lfloor\sqrt{n}\right\rfloor}-H_{\left\lfloor\sqrt{n}\right\rfloor}-\frac{\left\lfloor\sqrt{n}\right\rfloor}{n}.$$ Letting $n\to\infty$ you get the value of the limit $L_1$. If denoting $\left\lfloor\sqrt{n}\right\rfloor=m$, we have the type of limit mentioned above, $\lim_{m\to\infty}(H_{2m}-H_m)=\log(2)$.

Your limit, after replacing $n$ by $2n$, is

$$\lim_{n\to\infty}\sum_{k=1}^{2n}(-1)^{k-1}\frac{1}{2n}\left\lfloor\frac{2n}{k}\right\rfloor=\lim_{n\to\infty}\left(\sum_{k=1}^{2n}\frac{1}{2n}\left\lfloor\frac{2n}{k}\right\rfloor-2\sum_{k=1}^{n}\frac{1}{2n}\left\lfloor\frac{2n}{2k}\right\rfloor\right)$$ $$=\lim_{n\to\infty}\left(\sum_{k=1}^{2n}\frac{1}{2n}\left\lfloor\frac{2n}{k}\right\rfloor-\sum_{k=1}^{n}\frac{1}{n}\left\lfloor\frac{n}{k}\right\rfloor\right).$$

What's left to do? Using in the last limit that limit $L_1$ calculated above. $$\lim_{n\to\infty}\left(\sum_{k=1}^{2n}\frac{1}{2n}\left\lfloor\frac{2n}{k}\right\rfloor-\sum_{k=1}^{n}\frac{1}{n}\left\lfloor\frac{n}{k}\right\rfloor\right)$$ $$=\lim_{n\to\infty}\left(\sum_{k=1}^{2\left\lfloor \sqrt{n} \right\rfloor}\frac{1}{2n}\left\lfloor\frac{2n}{k}\right\rfloor+\sum_{k=2\left\lfloor \sqrt{n} \right\rfloor+1}^{2n}\frac{1}{2n}\left\lfloor\frac{2n}{k}\right\rfloor-\sum_{k=1}^{\left\lfloor \sqrt{n} \right\rfloor}\frac{1}{n}\left\lfloor\frac{n}{k}\right\rfloor-\sum_{k=\left\lfloor \sqrt{n} \right\rfloor+1}^n\frac{1}{n}\left\lfloor\frac{n}{k}\right\rfloor\right)$$ $$=\underbrace{\lim_{n\to\infty}\left(\sum_{k=1}^{2\left\lfloor \sqrt{n} \right\rfloor}\frac{1}{2n}\left\lfloor\frac{2n}{k}\right\rfloor-\sum_{k=1}^{\left\lfloor \sqrt{n} \right\rfloor}\frac{1}{n}\left\lfloor\frac{n}{k}\right\rfloor\right)}_{\displaystyle \log(2)}+\underbrace{\lim_{n\to\infty}\left(\sum_{k=2\left\lfloor \sqrt{n} \right\rfloor+1}^{2n}\frac{1}{2n}\left\lfloor\frac{2n}{k}\right\rfloor-\sum_{k=\left\lfloor \sqrt{n} \right\rfloor+1}^n\frac{1}{n}\left\lfloor\frac{n}{k}\right\rfloor\right)}_{\displaystyle 0}$$ $$=\log(2),$$ and the limit tending to $0$ can be done by arranging the sums under the limit under the form of an alternating sum and then squeezing the sum.

Further explanations on the limit tending to $0$

It's clear that $$0\le\sum_{k=2\left\lfloor \sqrt{n} \right\rfloor+1}^{2n}\frac{1}{2n}\left\lfloor\frac{2n}{k}\right\rfloor-\sum_{k=\left\lfloor \sqrt{n} \right\rfloor+1}^n\frac{1}{n}\left\lfloor\frac{n}{k}\right\rfloor=\frac{1}{2n}\sum_{k=\underbrace{2\left\lfloor \sqrt{n} \right\rfloor+1}_{m}}^{2n}(-1)^{k-1}\left\lfloor\frac{2n}{k}\right\rfloor$$ $$=\frac{1}{2n}\left(\left\lfloor\frac{2n}{m}\right\rfloor-\left\lfloor\frac{2n}{m+1}\right\rfloor+\left\lfloor\frac{2n}{m+2}\right\rfloor-\left\lfloor\frac{2n}{m+3}\right\rfloor+\left\lfloor\frac{2n}{m+4}\right\rfloor-\left\lfloor\frac{2n}{m+5}\right\rfloor+\left\lfloor\frac{2n}{m+6}\right\rfloor-\cdots\right)$$ $$\le\frac{1}{2n}\left(\left\lfloor\frac{2n}{m}\right\rfloor-\left\lfloor\frac{2n}{m+1}\right\rfloor+\left\lfloor\frac{2n}{m+1}\right\rfloor-\left\lfloor\frac{2n}{m+3}\right\rfloor+\left\lfloor\frac{2n}{m+3}\right\rfloor-\left\lfloor\frac{2n}{m+5}\right\rfloor+\left\lfloor\frac{2n}{m+5}\right\rfloor-\cdots\right)$$ $$=\frac{1}{2n}\left(\left\lfloor\frac{2n}{m}\right\rfloor-1\right)=\frac{1}{2n}\left(\left\lfloor\frac{2n}{2\left\lfloor \sqrt{n} \right\rfloor+1}\right\rfloor-1\right),$$ where letting $n\to\infty$, we obviously get $0$ which accounts for the limit tending to $0$ in my solution.

A final remark

One should have dealt from the very beginning with this part of the limit tending to $0$ since we had it in the form with the alternating sum as expected.