Let $x,y\in\Bbb R$ and $n\in\Bbb N$. Prove that, $$\sum_{k=0}^{n-1}\left \lfloor x+\dfrac{k}{n}\right \rfloor=\lfloor nx\rfloor.$$


We have to $x<\lfloor x\rfloor+1$. By adding $k/n$ to $x$, could be that $x+(k/n)$ keep being less than $\lfloor x\rfloor+1$, or they can be equal to or greater than it. We are going to have the following list of inequalities $$\begin{align*}\lfloor x\rfloor&\leq x+\dfrac{0}{n}<\lfloor x\rfloor +1\\ \lfloor x\rfloor &\leq x+\dfrac{1}{n}<\lfloor x\rfloor +1\\ & \vdots\\ \lfloor x\rfloor &\leq x+\dfrac i n<\lfloor x\rfloor +1\\ \lfloor x\rfloor +1&\leq x+\dfrac{i+1}{n}< \lfloor x\rfloor +2\\ &\vdots \\ \lfloor x\rfloor +1&\leq x+\dfrac {n-1} {n}<\lfloor x\rfloor +2 \end{align*} $$ where $ i $ is the maximum value of $ k $ so that the amount $ x + (k / n) $ does not reach $\lfloor x\rfloor+1$. So, $$\begin{align*}\sum_{k=0}^{n-1}\left \lfloor x+\dfrac{k}{n}\right \rfloor&=\sum_{k=0}^i \left \lfloor x+\dfrac{k}{n}\right \rfloor+\sum_{k=i+1}^{n-1}\left \lfloor x+\dfrac{k}{n}\right \rfloor\\ &=\sum_{k=0}^i \lfloor x\rfloor+\sum_{k=i+1}^{n-1} (\lfloor x\rfloor+1)\\ &= (i+1)\lfloor x\rfloor+(n-1-i)(\lfloor x\rfloor+1)\\ &=n\lfloor x\rfloor+n-i-1\\ &= \lfloor nx\rfloor +(n\lfloor x\rfloor-\lfloor nx\rfloor+n-i-1). \end{align*}$$ I got to that last part. I would only need to prove that $n\lfloor x\rfloor-\lfloor nx\rfloor+n-i-1=0$. Someone help me with that.


1 Answer 1


Let's write $x = \lfloor x \rfloor + \{x \}$, there exists $u \in \Bbb N, u \in \{ 0,...,(n-1)\}$ such that $$ \frac{u}{n}\le \{x \} < \frac{u+1}{n}$$ We have \begin{align} \sum_{k=0}^{n-1}\left \lfloor x+\dfrac{k}{n}\right \rfloor &= \sum_{k=0}^{n-1}\left \lfloor \lfloor x \rfloor +\{x \}+\dfrac{k}{n}\right \rfloor \\ &=n\lfloor x \rfloor+ \sum_{k=0}^{n-1}\left \lfloor \{x \}+\dfrac{k}{n}\right \rfloor \\ &=n\lfloor x \rfloor+ \sum_{k=0}^{n-1-u}\left \lfloor \{x \}+\dfrac{k}{n}\right \rfloor +\sum_{k=n-u}^{n-1}\left \lfloor \{x \}+\dfrac{k}{n}\right \rfloor \tag{1}\\ \end{align}

  • For $k = 0,...,(n-1-u)$:

$$\{x \}+\dfrac{k}{n}< \frac{u+1+k}{n}<1 \implies \sum_{k=0}^{n-1-u}\left \lfloor \{x \}+\dfrac{k}{n}\right \rfloor =0$$

  • For $k = (n-u),...,(n-1)$:

$$2>\{x \}+\dfrac{k}{n} \ge \frac{u+1+k}{n} \ge 1 \implies \sum_{k=n-u}^{n-1}\left \lfloor \{x \}+\dfrac{k}{n}\right \rfloor =(n-1)-(n-u)+1 = u$$

From $(1)$, we deduce then $$\sum_{k=0}^{n-1}\left \lfloor x+\dfrac{k}{n}\right \rfloor = n\lfloor x \rfloor+ u =n\lfloor x \rfloor +n\times \frac{u}{n} = n(\lfloor x \rfloor +\{x \}) = \lfloor nx \rfloor $$ Q.E.D


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .