Prove that $\left|\left\{\frac{n}{1}\right\} - \left\{\frac{n}{2}\right\} - \cdots - (-1)^n\left\{\frac{n}{n}\right\}\right| \le \sqrt{2n}$.

Question

For all positive integers $n$, prove that $$\large \left|\left\{\frac{n}{1}\right\} - \left\{\frac{n}{2}\right\} + \left\{\frac{n}{3}\right\} - \cdots - (-1)^n\left\{\frac{n}{n}\right\}\right| \le \sqrt{2n}$$

This is the last problem of a book I (wrongly) stole from the shelves from our class. And there definitely were shortcuts taken.

I also don't really understand the last part $$ [\cdots ]\le \frac{m - 2}{2} + \frac{n}{m} < \frac{\sqrt{2n} - 1}{2} + \sqrt{\frac{n}{2}} < 2n$$. Could someone please explain?

Moreover, the answer is lengthy, at least to me. So if you have any other solution that is shorter, please answer below and I would be appreciated.

Answer 1

Let $m = \lfloor\sqrt{2n} + 1\rfloor$. We have that $$\left|\left\{\frac{n}{1}\right\} - \left\{\frac{n}{2}\right\} + \left\{\frac{n}{3}\right\} - \cdots - (-1)^n\left\{\frac{n}{n}\right\}\right|$$

equals the absolute value of

$$\underbrace{\left(\left\{\frac{n}{1}\right\} + \left\{\frac{n}{2}\right\} - \left\{\frac{n}{3}\right\} + \cdots - (-1)^{m - 1}\left\{\frac{n}{m - 1}\right\}\right)}_{A}$$

$$ - (-1)^m\underbrace{\left(\frac{n}{m} + \frac{n}{m + 1} - \frac{n}{m + 2} + \cdots + (-1)^{n - m}\frac{m}{n}\right)}_{B}$$

$$ + (-1)^m\underbrace{\left(\left\lfloor\frac{n}{m}\right\rfloor + \left\lfloor\frac{n}{m + 1}\right\rfloor - \left\lfloor\frac{n}{m + 2}\right\rfloor + \cdots + (-1)^{n - m}\left\lfloor\frac{n}{n}\right\rfloor\right)}_{C}$$

Going through each term, we have that

$$ - \left(\left\{\dfrac{n}{2}\right\} + \left\{\dfrac{n}{4}\right\} + \left\{\dfrac{n}{6}\right\} + \cdots\right) \le A \le \left\{\dfrac{n}{1}\right\} + \left\{\dfrac{n}{3}\right\} + \left\{\dfrac{n}{5}\right\} + \cdots$$

with the expressions on the left- and right-hand side having $\left\lfloor\dfrac{m - 1}{2}\right\rfloor$ and $\left\lfloor\dfrac{m}{2}\right\rfloor$ respectively.

(It should be also noted that $\left\{\dfrac{n}{1}\right\} = 0$.)

For all $\left\{\dfrac{n}{p}\right\}$ $(p \in \mathbb Z^+, 1 \le p \le m)$, we have that $\left\{\dfrac{n}{p}\right\} \le \dfrac{p - 1}{p} \le \dfrac{m - 2}{m - 1}$

$$\implies |A| \le \left\lfloor\frac{m - 1}{2}\right\rfloor \cdot \dfrac{m - 2}{m - 1} \le \dfrac{m - 2}{2}$$

It is also evident that $$0 \le \left(\frac{m}{n} - \frac{n}{m + 1}\right) + \left(\frac{n}{m + 2} - \frac{n}{m + 3}\right) + \cdots $$

$$ = B = \frac{m}{n} - \left(\frac{n}{m + 1} - \frac{n}{m + 2}\right) - \cdots \le \dfrac{n}{m}$$

and $$0 \le \left(\left\lfloor\frac{m}{n}\right\rfloor - \left\lfloor\frac{n}{m + 1}\right\rfloor\right) + \left(\left\lfloor\frac{n}{m + 2}\right\rfloor - \left\lfloor\frac{n}{m + 3}\right\rfloor\right) + \cdots $$

$$ = B = \left\lfloor\frac{m}{n}\right\rfloor - \left(\left\lfloor\frac{n}{m + 1}\right\rfloor - \left\lfloor\frac{n}{m + 2}\right\rfloor\right) - \cdots \le \left\lfloor\dfrac{n}{m}\right\rfloor \le \dfrac{n}{m}$$

$$\implies \left|\left\{\frac{n}{1}\right\} - \left\{\frac{n}{2}\right\} + \left\{\frac{n}{3}\right\} - \cdots - (-1)^n\left\{\frac{n}{n}\right\}\right| = |A - (-1)^mB + (-1)^mC|$$

$$ \le \frac{m - 2}{2} + \frac{n}{m} < \frac{\sqrt{2n} - 1}{2} + \sqrt{\frac{n}{2}} < 2n$$