31
$\begingroup$

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?

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

3 Answers 3

14
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ 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$}? $\endgroup$
    – Tony Ma
    Apr 28, 2018 at 1:05
  • 1
    $\begingroup$ @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. $\endgroup$ Apr 28, 2018 at 2:36
  • $\begingroup$ Oic, I used to use the notation $\sum_{i\in\mathbb N:2i-1\le\frac{1}{x}\lt2i}1$ $\endgroup$
    – Tony Ma
    Apr 28, 2018 at 11:30
  • 1
    $\begingroup$ @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. $\endgroup$ Apr 28, 2018 at 12:30
  • 1
    $\begingroup$ 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 $\endgroup$
    – Tony Ma
    Apr 28, 2018 at 12:38
6
$\begingroup$

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

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

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.

$\endgroup$
4
  • $\begingroup$ Maybe you can add some step? such as how to use squeeze theorem and how my limit is equal to $L_1$? Thank you $\endgroup$
    – Tony Ma
    Apr 29, 2018 at 2:21
  • $\begingroup$ @TonyMa Is everything crystal clear now? $\endgroup$ Apr 29, 2018 at 9:55
  • $\begingroup$ 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? $\endgroup$
    – Tony Ma
    Apr 29, 2018 at 11:43
  • $\begingroup$ @TonyMa That's why I started with writing WLOG (without loss of generality). $s_{2k-1}$ follows the same line of proving the limit. $\endgroup$ Apr 29, 2018 at 11:48

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.