$\sum_{k=1}^n \lfloor kx \rfloor =$ ?

Question

Let $x$ be a positive real number and $n$ a positive integer , then how may we evaluate $\sum_{k=1}^n \lfloor kx \rfloor $ ?

If a closed form doesn't exist then can we at least find an asymptotic formula for the sum ?

Thanks in advance

Answer 1

If $x$ is irrational, then

$$ \sum_{k=1}^{n} \lfloor kx \rfloor = \sum_{k=1}^{n} kx - \sum_{k=1}^{n} \{ kx \} = \frac{n(n+1)x}{2} - n \cdot \frac{1}{n}\sum_{k=1}^{n} \{ kx \}. $$

Since the sequence $( \{ kx \} )$ is equidistributed, we know that

$$ \lim_{n\to\infty} \frac{1}{n}\sum_{k=1}^{n} \{ kx \} = \int_{0}^{1} x \, dx = \frac{1}{2}. $$

Consequently we have the following asymptotics:

$$ \sum_{k=1}^{n} \lfloor kx \rfloor = \tfrac{1}{2} x n^2 + \tfrac{1}{2}(x-1)n + o(n). $$

Answer 2

TheGreatDuck,

For $n \in \mathbb{N}$, $x \in \mathbb{R}$ we have $$ \lfloor nx \rfloor = \sum\limits_{i=0}^{n-1} \lfloor x + \frac{i}{n} \rfloor $$