Show that if $x\geq 0$ and $n$ is a positive integer, then $\sum_{k=0}^{n-1}\left\lfloor {x+\frac{k}{n}}\right\rfloor=\lfloor {nx}\rfloor$

Question

I need help with this question, where $\lfloor x\rfloor$ means the floor function of $x$.

Show that if $x\geq 0$ and $n$ is a postive integer, then $$\sum_{k=0}^{n-1}\left\lfloor x+\frac{k}{n} \right\rfloor =\lfloor nx\rfloor$$

Answer 1

The main idea of the proof is splitting the $x$ into integer and fractional part. That is, $x=\lfloor x \rfloor+{x}$ and there exists exactly one $k' \in \{1,2, \dots n \}$.

$$\lfloor x\rfloor=\left \lfloor x+\frac{k'-1}{n}\right\rfloor\le x\left\lfloor x+\frac{k'}{n}\right\rfloor=\lfloor x\rfloor+1 $$

Subtracting $\lfloor x \rfloor$ from the equation would give:

$$\left\lfloor \{x\}+\frac{k'-1}{n}\right\rfloor\le \{x\} \left\lfloor \{x\}+\frac{k'}{n}\right\rfloor=1$$

$$1-\frac{k'}{n}\le \{x\} < 1-\frac{k'-1}{n}$$

Multiplying out $n$ throughout.

$$\sum_{k=0}^{n-1}\left\lfloor x+\frac{k}{n}\right\rfloor =\sum_{k=0}^{k'-1} \lfloor x\rfloor+\sum_{k=k'}^{n-1} (\lfloor x\rfloor+1)=n\, \lfloor x\rfloor+n-k'$$

$$=n\, \lfloor x\rfloor+\lfloor n\,\{x\}\rfloor=\left\lfloor n\, \lfloor x\rfloor+n\, \{x\} \right\rfloor=\lfloor nx\rfloor$$

Source: Hermite's Identity.

Answer 2

Here is a solution I saw many many years ago and really love:

Let $f(x)=\sum_{k=0}^{n-1}\lfloor x+\frac{k}{n}\rfloor -\lfloor nx\rfloor$.

Then $$f(x+\frac{1}{n})= \sum_{k=0}^{n-1}\lfloor x+\frac{k}{n}+\frac{1}{n}\rfloor -\lfloor nx+1\rfloor= \sum_{k=1}^{n}\lfloor x+\frac{k}{n}\rfloor -\lfloor nx\rfloor -1 $$ $$=\sum_{k=1}^{n-1}\lfloor x+\frac{k}{n}\rfloor +\lfloor x+1 \rfloor-\lfloor nx\rfloor -1 =\sum_{k=1}^{n-1}\lfloor x+\frac{k}{n}\rfloor +\lfloor x \rfloor-\lfloor nx\rfloor =f(x) $$

Thus $f$ is periodic with period $\frac{1}{n}$.

Moreover, if $x \in [0, \frac{1}{n})$ then

$$f(x)=\sum_{k=1}^{n-1}0-0=0 \,.$$

Thus $f$ is periodic with period $T=\frac{1}{n}$ and zero on $[0,T)$, hence $f$ is the zero function.

Answer 3

For given $x\in{\mathbb R}$ write $$x=j+{r\over n}+\xi\qquad{\rm with}\qquad j\in{\mathbb Z}, \quad 0\leq r<n, \quad 0\leq\xi<{1\over n}\ .$$ Then $$\lfloor nx\rfloor=\lfloor nj + r+n\xi\rfloor=nj+r\ .$$ On the other hand $$\left\lfloor x+{k\over n}\right\rfloor=\left\lfloor j+{r+k\over n}\right\rfloor=\cases{j\quad&$(0\leq k<n-r)$ \cr j+1\quad&$(n-r\leq k<n)$\cr}$$ and therefore $$\sum_{k=0}^{n-1}\left\lfloor x+{k\over n}\right\rfloor= nj + r\ ,$$ as above.