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