Exercise 4.1.37** ($\sum_{k=1}^n\lfloor kx \rfloor/k \leq \lfloor nx \rfloor$)

Question

Show that if $x$ is a real number and $n$ is a positive integer, then $\sum_{k=1}^n\lfloor kx \rfloor/k \leq \lfloor nx \rfloor$.

Richard Ganaye · Accepted Answer

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

I give here the simplest solution found on the net.
\begin{verbatim}
https://math.stackexchange.com/questions/1699718/
is-true-that-sum-k-1n-frackxk-leqnx-for-every-x-in-mathbbr-an
\end{verbatim}
\begin{proof} 
Define $S_0(x) = 0$ and for all positive integer $n$, for all $x \in \R$,
$$S_n(x) = \sum_{k=1}^n\frac{\lfloor kx floor}{k}.$$
For $k\geq 1$,  $S_{k}(x) - S_{k-1}(x) = \frac{\lfloor kx floor }{k}$, thus
\begin{align}
kS_k(x) - (k-1) S_{k-1}(x) = S_{k-1}(x) + \lfloor kx floor.
\end{align}
The sum of these equalities for $k=1,2, \ldots, n$ gives
\begin{align*}
nS_n(x) &= \sum_{k=1}^n (kS_k(x) - (k-1) S_{k-1}(x)).
\end{align*}
and by equality (1),
\begin{align}
nS_n(x)&=\sum_{k=1}^n S_{k-1}(x) +\sum_{k=1}^n \lfloor kx floor.
\end{align}
$S_0(x) = 0 \leq \lfloor 0\cdot x floor$. Reasoning by strong induction, suppose that for some $n \in \N^*$, 
$$\mathscr{P}(n): \forall k \in \N,\  k<n  \Rightarrow ( \forall x \in \R,\ S_k(x) \leq \lfloor k x floor)$$
is true, so that $S_0(x) \leq \lfloor 0\cdot x floor, S_1(x) \leq \lfloor  x floor, \ldots, S_{n-1}(x) \leq \lfloor (n-1) x floor$.

By the induction hypothesis, 
\begin{align*}
&\sum_{k = 1}^n S_{k-1}(x) \leq \sum_{k = 1}^n \lfloor (k-1) x floor = \sum_{j = 0}^{n-1} \lfloor j x floor &(j = k-1),
\end{align*}
so by (2),
\begin{align*}
nS_n(x) &=\sum_{j = 0}^{n-1} \lfloor j x floor + \sum_{k=1}^n \lfloor kx floor\
&= \sum_{j = 0}^{n-1} \lfloor j x floor + \sum_{j=0}^{n-1} \lfloor (n-j)x floor & (j = n -k)\
&=\sum_{j = 0}^{n-1} (\lfloor j x floor +  \lfloor (n-j)x floor) \
&\leq \sum_{j = 0}^{n-1} \lfloor n x floor & (	ext{by Theorem 4.1 (4)})\
&= n \lfloor n x floor.
\end{align*}
Thus $S_n(x) \leq \lfloor nx floor$, so $\mathscr{P}(n+1)$ is true.

The induction is done, which proves that for all positive integers,
$$\sum_{k=1}^n\frac{\lfloor kx floor}{k} \leq \lfloor nx floor.$$
\end{proof}

Exercise 4.1.37** ($\sum_{k=1}^n\lfloor kx \rfloor/k \leq \lfloor nx \rfloor$)

Answers

Comments

Exercise 4.1.37** ($\sum_{k=1}^n\lfloor kx \rfloor/k \leq \lfloor nx \rfloor$)

Answers

Comments

Add answer