Proving the Floor of nx using Fractional Parts and Induction

[Ragnarok7]

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

Note \(\displaystyle \lfloor x\rfloor\) means the greatest integer less than or equal to \(\displaystyle x\).

I proved the cases where n=2 and n=3 by writing \(\displaystyle x=\lfloor x\rfloor + \{x\}\), where \(\displaystyle \{x\}\) is the fractional part of \(\displaystyle x\), and then using cases where \(\displaystyle 0\leq \{x\}<\frac{1}{n}\), \(\displaystyle \frac{1}{n}\leq \{x\}<\frac{2}{n}\), \(\displaystyle \ldots\), \(\displaystyle \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.