Proving the Floor of nx using Fractional Parts and Induction

[Ragnarok7]

Prove that $$\lfloor nx \rfloor = \sum_{k=0}^{n-1}\lfloor x+k/n \rfloor$$.

Note $$\lfloor x\rfloor$$ means the greatest integer less than or equal to $$x$$.

I proved the cases where n=2 and n=3 by writing $$x=\lfloor x\rfloor + \{x\}$$, where $$\{x\}$$ is the fractional part of $$x$$, and then using cases where $$0\leq \{x\}<\frac{1}{n}$$, $$\frac{1}{n}\leq \{x\}<\frac{2}{n}$$, $$\ldots$$, $$\frac{n-1}{n}\leq\{x\}<1$$. However, this is tedious and doesn't work in the general case. Does anyone have any suggestions for showing this? I don't see that induction will help.

Thank you!

 

[magneto1]

The outline of a proof goes something like this.

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

Show $f$ has the properties:

$(i)$: $f(x + \frac 1n) = f(x)$, and
$(ii)$: $f(x) = 0$ for $0 \leq x < \frac 1n$.

Then, claim that if $f$ has properties $(i)$ and $(ii)$, $f \equiv 0$, and thus the original equality holds.

 

[johng1]

Magneto, very clever. Well done.

 

[Ragnarok7]

Thank you! That is great and very simple. Can I ask how you got the idea to do it this way? I would never have thought of it.