I conjecture inequalities $\sum_{k=1}^{n}\{kx\}\le\frac{n}{2}x$

As მამუკა ჯიბლაძე said, the proof is a picture though I had trouble reconstructing the picture of his and came up with a slightly different one.

Let $0<y<1$. Consider the rectangles with bases $[k-1,k]$ of heights $[ky]$ for $k=1,2,\dots,n$. They cover the triangle with the vertices $(0,0),(n,0),(n,ny)$ up to several triangles of height $\le 1$ with sum of bases $\le n$. This proves the inequality $$ \sum_{k=1}^n[ky]\ge \frac{n^2y}2-\frac n2\,. $$ Now, for $x=1+y\in(1,2)$, we have $$ \sum_{k=1}^n\{kx\}=\sum_{k=1}^n\{ky\}=\sum_{k=1}^n ky-\sum_{k=1}^n[ky] \\ \le \frac{n(n+1)y}2-\frac{n^2y}2+\frac n2=\frac n2(1+y)=\frac n2x\,. $$

Here is a different, more algebraic proof. I don't know if there is any reason to prefer it to the visual proof.

It is sufficient to prove the inequality if we take $\{x\}$ to round up instead of down, as that is a stronger inequality.

If we raise $x$ by $\epsilon$, where $\epsilon$ is small enough that no fractional part wraps around, the left side increases by $n (n+1) \epsilon/2$ and the right side by $n \epsilon/2$. We can do this unless $xk$ is an integer for some $1 \leq k \leq n$. Because the increase on the left is greater than the increase on the right, we can reduce to the case where $xk$ is an integer for some $1 \leq k \leq n$, say $x=a/b$ with $1 \leq b \leq n$ and $a,b$ relatively prime. We have

$$ \sum_{k=1}^n \left\{ k \frac{a}{b} \right\} = \sum_{k=1}^b \left\{ k \frac{a}{b} \right\} +\sum_{k=b+1}^n \left\{ k \frac{a}{b} \right\} $$

For the first term, we use the fact that $a$ is a permutation of residue classes mod $b$, so

$$ \sum_{k=1}^b \left\{ k \frac{a}{b} \right\} = \sum_{k=1}^b \left\{ \frac{k}{b} \right\}= \sum_{k=1}^b \frac{k}{b} = \frac{b (b+1)}{2b} \leq \frac{b a}{2b} = \frac{bx}{2} $$

For the second term, we use periodicity and induction on $n$, so

$$\sum_{k=b+1}^n \left\{ k \frac{a}{b} \right\} = \sum_{k=1}^{n-b} \left\{ k \frac{a}{b} \right\} \leq \frac{ (n-b) x}{2} $$

Summing, we get an upper bound of $\frac{nx}{2}$, as desired (and as necessary for the induction step).

This is a proof smilar to Will Sawin's but with no induction.

Set $y=x-1$. We need to prove that the average of $\{y\},\dots,\{ny\}$ is at most $x/2$. The numbers $y,2y,\dots,ny$ split into contiguous groups, each group with the same integer part. It suffices to show that the average of the fractional parts for each group is at most $x/2$. Those fractional parts form an arithmetical sequence, so their average is half the sum of the first and the last term. As the fractional part of the first term in the group is at most $y$, this average is bounded by $\frac{y+1}2=x/2$, as desired.