Why must $n-\lfloor\frac n2\rfloor+\lfloor\frac n3\rfloor-\dotsb$ grow like $n\ln2$?

161 Views Asked by At

Let $$a(n):=n-\left\lfloor\frac n2\right\rfloor+\left\lfloor\frac n3\right\rfloor-\left\lfloor\frac n4\right\rfloor+\left\lfloor\frac n5\right\rfloor-\dotsb.$$ Note that this is a finite sum. Naïvely, $$a(n)\approx n-\frac n2+\frac n3-\frac n4+\frac n5-\dotsb=n\ln2,$$ and so in particular \begin{align}\lim_{n\to\infty}\frac{a(n)}n=\ln2.\tag{$*$}\end{align} However, I'm having trouble proving this formally. In particular, the difficulty lies in showing that the error goes to zero.

The OEIS page for this sequence, https://oeis.org/A059851, claims that $(*)$ is correct, but I have been unable to prove it. Can someone find a rigorous proof?

1

There are 1 best solutions below

3
On BEST ANSWER

Let $S_n = \sum_{k=1}^{n} \frac{(-1)^{k-1}}{k} $ denote the partial sum of the alternating harmonic series. Then

\begin{align*} \frac{a(n)}{n} - S_n &= \sum_{k=1}^{n} (-1)^{k-1} \left( \left\lfloor\frac{n}{k}\right\rfloor - \frac{n}{k} \right)\frac{1}{n} \\ &= \sum_{k=1}^{n} \left( \left\lfloor\frac{n}{k}\right\rfloor - \frac{n}{k} \right)\frac{1}{n} - \sum_{k=1}^{\lfloor n/2\rfloor} \left( \left\lfloor\frac{n}{2k}\right\rfloor - \frac{n}{2k} \right)\frac{2}{n} \\ &\to \int_{0}^{1} \left( \left\lfloor\frac{1}{x}\right\rfloor - \frac{1}{x} \right) \, \mathrm{d}x - \int_{0}^{1} \left( \left\lfloor\frac{1}{x}\right\rfloor - \frac{1}{x} \right) \, \mathrm{d}x \\ &= 0. \end{align*}

Here, we utilized the fact that $x \mapsto \left\lfloor\frac{1}{x}\right\rfloor - \frac{1}{x}$ (with a suitable modification at $x=0$) is Riemann integrable on $[0, 1]$.