How to prove that : $\sum \limits_{k=0}^{n-1} \lfloor x+\frac{k}{n}\rfloor = \lfloor nx\rfloor$?

Question

for all $x\in \mathbb{R}$ and $n\in\mathbb{N}^*$ without using euclidian division.

First I re-write the sum in this way : $\sum \limits_{k=0}^{n-1} \lfloor x+\frac{k}{n}\rfloor = \lfloor x\rfloor+\lfloor x+\frac{1}{n}\rfloor+... +\lfloor x+\frac{i-1}{n}\rfloor+ \lfloor x+1-\frac{i}{n}\rfloor+...+\lfloor x+1-\frac{1}{n}\rfloor$

Now we can see that there is two possibilities for $x$ between two natural numbers $[q,q+1]$. Indeed we have the part $\sum \limits_{k=0}^{i-1}\lfloor x+\frac{k}{n}\rfloor=ji$ with $0\le j\le n$.And the other part $\sum \limits_{k=i}^{n-1}\lfloor x+1-\frac{k}{n}\rfloor=(j+1)(n-i)$.

Finally the floor will be $nj+(n-i)$.

Now for $\lfloor nx \rfloor$ it will be between $[nq,nq+q]$ which lets $n$ possibilities for its values but it would be perfect if it was $nj+(n-i)$ .

Thanks in advance !

Answer 1

Write $x=m+\epsilon,\epsilon\in[0,1)$. Let $K\in \{0,\dots,n\}$ be the smallest integer such that $\epsilon+K/n\geq 1$. Then $K=\lceil(1-\epsilon)n\rceil$ \begin{align*}\sum_{k=0}^{n-1}\lfloor x+k/n\rfloor& =\sum_{k=0}^{K-1}\lfloor x+k/n\rfloor+\sum_{k=K}^{n-1}\lfloor x+k/n\rfloor\\ & =Km+(n-K)(m+1)\\ & =nm+(n-K)\\ & = nm+(n-\lceil(1-\epsilon)n\rceil)\\ & = nm-\lceil-n\epsilon \rceil\\ & = nm+\lfloor n \epsilon \rfloor\\ & = \lfloor nx\rfloor \end{align*} Where I used that the floor and ceiling function are linear on $\mathbb{N}$ and $-\lceil -x\rceil=\lfloor x\rfloor$

Answer 2

Let $x = q + \{x\}$ where $q \in \mathbb{N}$ and $\{x\}$ is the fractional part of $x$. For some natural number $0\leq j \leq n -1$, we have $j \leq n\cdot \{x\} < j + 1$. Then $\lfloor nx\rfloor = nq + j$.

$$\sum_{k=0}^{n-1} \left\lfloor x + \frac{k}{n} \right\rfloor = nq + \sum \left\lfloor\{x\} + \frac{k}{n}\right\rfloor$$

For $0\leq k \leq n - j - 1$, we know that $\left\lfloor\{x\} + \frac{k}{n}\right\rfloor = 0$, and when $n - j \leq k \leq n-1$, $\left\lfloor\{x\} + \frac{k}{n}\right\rfloor = 1$.. Therefore:

$$\sum \left\lfloor\{x\} + \frac{k}{n}\right\rfloor = j$$