TITLE: How to prove that : $\sum \limits_{k=0}^{n-1} \lfloor x+\frac{k}{n}\rfloor = \lfloor nx\rfloor$?
QUESTION [3 upvotes]: 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 !

REPLY [2 votes]: 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$$

REPLY [2 votes]: 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$
{"set_name": "stack_exchange", "score": 3, "question_id": 1914565}