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.
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?
Best Answer
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:
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. $$