# Summing $dn$ floor functions = $d$ times Summing $n$ floor functions

Fix integer $d>1$, and assume real number $x\in[0,1]$.
I claim the following statement:
$\sum_{k=1}^{dn}\lfloor kx\rfloor=d\sum_{k=1}^n\lfloor kx\rfloor$ is true iff $x\in[0,\frac{1}{dn}]$.

I can check it in various cases, and the if-direction is obvious. But my combinatorics skills are not sharp, so is there a counterexample?

-

## 1 Answer

You must have $x \in \left[0,\frac{1}{dn}\right)$, for if $x = \frac{1}{dn}$, then the left hand side is $1$, and the right hand side is $0$.

Generally, if $\frac{1}{dn} \leqslant x < \frac{1}{n}$, then

$$d\sum_{k=1}^n \lfloor kx\rfloor = 0 < \lfloor dnx\rfloor \leqslant \sum_{k=1}^{dn} \lfloor kx\rfloor,$$

so in that case you don't have equality. And if $x \geqslant \frac1n$, then you have

\begin{align} \sum_{k=1}^{dn} \lfloor kx\rfloor - d\sum_{k=1}^n \lfloor k\rfloor &= \sum_{j=0}^{d-1} \left(\sum_{k=1}^n \left(\lfloor (k+jn)x\rfloor - \lfloor kx\rfloor\right)\right)\\ &\geqslant\sum_{j=0}^{d-1} \sum_{k=1}^n\left(\lfloor kx + j\rfloor - \lfloor kx\rfloor\right)\\ &\geqslant \sum_{j=0}^{d-1} nj\\ &= n\frac{d(d-1)}{2}\\ &> 0. \end{align}

-
@DanielFisher, if in addition I have the starting value to be scaled by $d$, i.e. $\sum^{dn}_{k=dk_0}$ and $d\sum^n_{k=k_0}$, do we stumble across a problem? – Chris Gerig Oct 24 '13 at 0:18
One problem is the number of summands. $\sum_{k=dk_0}^{dn}$ gives $d(n-k_0+1)+1$ values, $\sum_{k=k_0}^n$ gives $(n-k_0+1)$ values, so if the terms scaled exactly with $d$, you'd have an extra term. Depending on how that is handled, the range for which both sums have the same value ($0$) may be changed slightly ($x \in \left[0,\frac{1}{dn-1}\right)$ if the $k = dn$ term is omitted), but the strict inequality remains for larger $x$. – Daniel Fischer Oct 24 '13 at 8:12
@DanielFisher, Oh sorry there's a typo. It should be $\sum^{dn}_{k=dk_0+1}$ and $d\sum^{n}_{k=k_0+1}$. Not sure how much this affects your statement, but I don't see exactly how dropping the $k=dn$ term gives us this new range (which I unfortunately can't drop). Ultimately I'm trying to take the original equality that I wrote in the question, and subtract from it the same equality but with smaller $n$. – Chris Gerig Oct 24 '13 at 8:52
If you only sum to $dn-1$, the largest term is $\lfloor (dn-1)x\rfloor$, for $x < \frac{1}{dn-1}$, that is $0$, hence all terms are $0$. But since you keep the upper limit and change the lower limit, that's not relevant. By the way, I mixed up the counts in the previous comment, not yet fully awake. I'm not sure I understand what you're trying to do. You take $\sum_{k=1}^{dn} \lfloor kx\rfloor = d\sum_{k=1}^n \lfloor kx\rfloor$ for $0 \leqslant x < \frac{1}{dn}$, and then subtract $\sum_{k=1}^{dm}\lfloor kx\rfloor = d\sum_{k=1}^m\lfloor kx\rfloor$ from it, for some $m < n$? And then? – Daniel Fischer Oct 24 '13 at 9:03
Ah no sorry, I'm looking for the true range of x after I form the new 'equality'. – Chris Gerig Oct 24 '13 at 9:12