# $\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

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?

• (+1), this question takes "shows research effort" to a new level! – John Doe Apr 27 '18 at 12:41
• Why does the first link go to desmos instead of Brilliant? – Barry Cipra Apr 27 '18 at 13:18
• Corrected. Thx. – Tony Ma Apr 28 '18 at 0:45
• Related question: math.stackexchange.com/questions/115824/… – Aryabhata Apr 28 '18 at 1:36

## 3 Answers

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

• Sorry, I don't understand your notation in line 1: How can you sum from $i=1$ to $\infty$ but also requiring {$2i-1\le\frac{1}{x}\lt 2i$}? – Tony Ma Apr 28 '18 at 1:05
• @TonyMa, The notation $\mathbf{1}_{\{\cdots\}}$ yields $1$ if $\cdots$ is true and $0$ otherwise. I just partitioned the set $$A = \{ x \in [0, 1] : \text{x > 0 and \lfloor 1/x \rfloor is odd}\}$$ into $$A = \bigcup_{i=1}^{\infty} \{ x \in (0, 1] : 2i-1 \leq (1/x) < 2i \},$$ which yields the first line. In particular, at most one term in $\sum_{i=1}^{\infty} \mathbf{1}_{\{ 2i-1 \leq \frac{1}{x} < 2i \}}$ is non-zero. – Sangchul Lee Apr 28 '18 at 2:36
• Oic, I used to use the notation $\sum_{i\in\mathbb N:2i-1\le\frac{1}{x}\lt2i}1$ – Tony Ma Apr 28 '18 at 11:30
• @TonyMa, Since the discontinuities of $f$ occur at $\{\frac{1}{n}:n\geq 1\}\cup\{0\}$, it is not hard to directly establish the Riemann integrability. But of course we can count on a sledgehammer method; it can be proved that a bounded function is Riemann integrable if and only if the set of discontinuities is measure-zero. – Sangchul Lee Apr 28 '18 at 12:30
• I think I understand it. How a wonderful solution! I have think up the idea of this approach but I haven't try to use $f(\frac{j}{n})$ to make it be a Riemann sum. Truly beautiful. Thank so much – Tony Ma Apr 28 '18 at 12:38

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

• For first sentence, do you assume $n$ is even? For second, do you mean $\ln$ instead of $\log$? – Tony Ma Apr 28 '18 at 0:51
• @TonyMa usually $\log$ and $\ln$ are used interchangeably. – John Doe Apr 28 '18 at 3:48
• @TonyMa No, $n$ is any integer number. I mean $\ln$. – Robert Z Apr 28 '18 at 5:48

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)}_\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)}_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.

• Maybe you can add some step? such as how to use squeeze theorem and how my limit is equal to $L_1$? Thank you – Tony Ma Apr 29 '18 at 2:21
• @TonyMa Is everything crystal clear now? – user 1357113 Apr 29 '18 at 9:55
• Well...Sounds pretty cool. I get your idea and I think I might study it carefully later. But do you just proof one of the subsequences $s_{2k}\to\ln2$? How about $s_{2k-1}$? Or do u know it also converges to $\ln 2$ for sure? Does it have a similar proof? – Tony Ma Apr 29 '18 at 11:43
• @TonyMa That's why I started with writing WLOG (without loss of generality). $s_{2k-1}$ follows the same line of proving the limit. – user 1357113 Apr 29 '18 at 11:48