Is true that $\sum_{k=1}^n\frac{[kx]}{k}\leq[nx]$, for every $x\in\mathbb{R}$ and for every $n\in\mathbb{Z}^+$?

Is true that $\displaystyle\sum_{k=1}^n\dfrac{[kx]}{k}\leq[nx]$, for every $x\in\mathbb{R}$ and for every $n\in\mathbb{Z}^+$?

My work:

Let $x\in\mathbb{R}$ be given. For every $k=1,\dots,n$, define $i_k\in\{0,1,\dots,k-1\}$ such that $$ [x]+\frac{i_k}{k}\leq x<[x]+\frac{i_k+1}{k}\hspace{20mm} (*). $$

On one hand, we have that $[kx]=k[x]+i_k$ for every $k=1,\dots,n$.

So $\displaystyle\sum_{k=1}^n\dfrac{[kx]}{k}=n[x]+\displaystyle\sum_{k=1}^n\dfrac{i_k}{k}=[nx]+\displaystyle\sum_{k=1}^n\dfrac{i_k}{k}-i_n$

Thus $$\displaystyle\sum_{k=1}^n\dfrac{[kx]}{k}\leq[nx]\Leftrightarrow\displaystyle\sum_{k=1}^n\dfrac{i_k}{k}\leq i_n\,.$$

On the other hand, from $(*)$ is direct that $i_k=[k(x-[x])]$. Thus $$\displaystyle\sum_{k=1}^n\dfrac{[kx]}{k}\leq[nx]\Leftrightarrow\displaystyle\sum_{k=1}^n\dfrac{[k(x-[x])]}{k}\leq [n(x-[x])]\,.$$

In other words, we can assume that $x\in[0,1)$.

Now the questions is:

Is true that $\displaystyle\sum_{k=1}^n\dfrac{[kx]}{k}\leq[nx]$, for every $x\in[0,1)$ and for every $n\in\mathbb{Z}^+$?

Any simpler approach? Any thoughts?

Solution 1:

Note that the function $$f:\mathbb{R}\to\mathbb{R},f(x)=[nx]-\sum_{k=1}^n\frac{[kx]}{k}$$ is right-continuous and $1$-periodic function, so it is enough to prove that $f(x)\ge0$ for $x\in[0,1)$. Note also that the set of points of discontinuity of $f$ on $(0,1)$ is contained in $$\mathcal{D}=\left\{\frac{p}{q}: 1\le p< q\le n,\gcd(p,q)=1\right\}$$ and that $f$ is constant on any interval contained in $[0,1)\setminus\mathcal{D}$. Therefore, in order to prove that $f(x)\ge0$ on $(0,1)$ it is enough to prove that $f(r)\ge0$ for $r\in\mathcal{D}$.

Now, consider $r=p/q\in\mathcal{D}$ with $1\le p<q\le n$ and $\gcd(p,q)=1$. For $k\in\{1,\ldots,q-1\}$ we define $\phi(k)=pk-q[kr]$. Since $[kr]\le kr<[kr]+1$ we see that $0\le\phi(k)<q$, moreover, if $\phi(k)=0$ for some $k$ we conclude that $q$ must divide $k$, beause $\gcd(p,q)=1$, which is absurd. Thus $\phi$ takes its values in $\{1,\ldots,q-1\}$. Further, $\phi$ is one to one, because if $\phi(k)=\phi(\ell)$ for some $1\le k\le\ell<q$ we conclude that $q|(p(\ell-k))$ and again, because $\gcd(p,q)=1$ we see that $q|(\ell-k)$ and this implies that $\ell=k$ because $0\le \ell-k<q$. Thus, $\phi$ is a permutation on the set $\{1,\ldots,q-1\}$.

Using the AM-GM inequality we have $$\frac{1}{q-1}\sum_{k=1}^{q-1}\frac{\phi(k)}{k}\ge\left(\prod_{k=1}^{q-1}\frac{\phi(k)}{k}\right)^{1/(q-1)}=1$$ because $\phi(1)\phi(2)\cdot\phi(q-1)=1\cdot 2\cdots(q-1)$.

Thus $$\sum_{k=1}^{n}\frac{kp-q[kr]}{k}\ge\sum_{k=1}^{q-1}\frac{kp-q[kr]}{k}\ge q-1 \ge pn-q[nr]$$ Rearranging we get $f(r)\ge0$ which is the desired conclusion. The proof is complete.