Formula$$\sum_{k=0}^{n-1}\lfloor{x+\dfrac{k}{n}}\rfloor=\lfloor nx \rfloor$$

where $\lfloor a \rfloor$ means the integer part function, sometimes called "floor" function (ex.: $\lfloor 3.4\rfloor=3).$

is one of the fundamental properties of integer part function.

I have to establish it but I have no idea of even how to start.

Can you help me ?

  • 3
    $\begingroup$ start by supposing $\frac{i}{n}\leq x-[x] < \frac{i+1}{n}$, then compute both sides $\endgroup$ – Petite Etincelle Aug 19 '16 at 20:50

Using the change of variable $u=nx$, the desired identity is equivalent to showing

$$f(u)=\lfloor u\rfloor-\sum_{k=0}^{n-1}\left\lfloor u+k\over n\right\rfloor=0$$

for all $u$.

It's easy to see that $f(u)=0$ for $0\le u\lt1$. But we also have

$$\begin{align} f(u+1)&=\lfloor u+1\rfloor-\sum_{k=0}^{n-1}\left\lfloor u+1+k\over n\right\rfloor\\ &=\lfloor u+1\rfloor-\sum_{k=1}^{n}\left\lfloor u+k\over n\right\rfloor\\ &=\lfloor u+1\rfloor-\sum_{k=0}^{n-1}\left\lfloor u+k\over n\right\rfloor+\left\lfloor u+0\over n\right\rfloor-\left\lfloor u+n\over n\right\rfloor\\ &=\lfloor u\rfloor+1-\sum_{k=0}^{n-1}\left\lfloor u+k\over n\right\rfloor+\left\lfloor u\over n\right\rfloor-\left(\left\lfloor u\over n\right\rfloor+1\right)\\ &=\lfloor u\rfloor-\sum_{k=0}^{n-1}\left\lfloor u+k\over n\right\rfloor\\ &=f(u) \end{align}$$

so the function $f$ is periodic with period $1$, hence simply repeats the constant value $0$ from the interval $0\le u\lt1$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy