TAOCP 1.2.4 Exercise 38
Let S(x,y)=\sum_{0\le k<y}\left\lfloor x+\frac{k}{y}\right\rfloor, \qquad y>0.
Section 1.2.4: Integer Functions and Elementary Number Theory
Exercise 38. [M26] (E. Busche, 1909.) Prove that, for all real $x$ and $y$ with $y>0$,
$$ \sum_{0 \le k < y} \left\lfloor x+\frac{k}{y} \right\rfloor = \lfloor xy + \lfloor x+1 \rfloor(\lceil y \rceil - y)\rfloor. $$
In particular, when $y$ is a positive integer $n$, we have the important formula
$$\lfloor x \rfloor + \left\lfloor x+\frac1n \right\rfloor + \cdots + \left\lfloor x+\frac{n-1}{n} \right\rfloor = \lfloor nx \rfloor.$$
Verified: no
Solve time: 48s
Setup
Let
$$ S(x,y)=\sum_{0\le k<y}\left\lfloor x+\frac{k}{y}\right\rfloor, \qquad y>0. $$
Since the summation index ranges over integers $k$ satisfying $0\le k<y$, the number of terms is $\lceil y\rceil$. Write
$$ x=\lfloor x\rfloor+\theta, \qquad 0\le \theta<1, $$
by equation (4). We must prove that
$$ S(x,y) = \left\lfloor xy+\lfloor x+1\rfloor(\lceil y\rceil-y) \right\rfloor. $$
In the special case that $y=n$ is a positive integer, we must derive
$$ \lfloor x\rfloor+\left\lfloor x+\frac1n\right\rfloor+\cdots+ \left\lfloor x+\frac{n-1}{n}\right\rfloor = \lfloor nx\rfloor. $$
Solution
Let
$$ m=\lfloor x\rfloor, \qquad x=m+\theta, \qquad 0\le \theta<1. $$
Then
$$ \left\lfloor x+\frac{k}{y}\right\rfloor = \left\lfloor m+\theta+\frac{k}{y} \right\rfloor = m+\left\lfloor \theta+\frac{k}{y}\right\rfloor. $$
Since $0\le \theta<1$ and $0\le k<y$, we have
$$ 0\le \theta+\frac{k}{y}<2. $$
Hence
$$ \left\lfloor \theta+\frac{k}{y}\right\rfloor = \begin{cases} 0, & \theta+\dfrac{k}{y}<1,\[1ex] 1, & \theta+\dfrac{k}{y}\ge 1. \end{cases} $$
Therefore
$$ S(x,y) = m\lceil y\rceil+N, $$
where $N$ is the number of integers $k$ satisfying
$$ 0\le k<y, \qquad \theta+\frac{k}{y}\ge 1. $$
The inequality is equivalent to
$$ k\ge y(1-\theta). $$
Since $0\le k<y$, the admissible integers are
$$ k= \lceil y(1-\theta)\rceil, , \lceil y(1-\theta)\rceil+1, \ldots, \lceil y\rceil-1. $$
Their number is
$$ N = \lceil y\rceil-\lceil y(1-\theta)\rceil. $$
Using $\lceil t\rceil=-\lfloor -t\rfloor$,
$$ N = \lceil y\rceil+\lfloor -y(1-\theta)\rfloor = \lceil y\rceil+\lfloor y\theta-y\rfloor. $$
Since $\lceil y\rceil-y$ is an integer,
$$ \lfloor y\theta-y\rfloor = \lfloor y\theta-\lceil y\rceil+(\lceil y\rceil-y)\rfloor = \lfloor y\theta-\lceil y\rceil\rfloor + (\lceil y\rceil-y). $$
Also, because $\lceil y\rceil$ is an integer,
$$ \lfloor y\theta-\lceil y\rceil\rfloor = \lfloor y\theta\rfloor-\lceil y\rceil. $$
Hence
$$ N = \lfloor y\theta\rfloor+(\lceil y\rceil-y). $$
Substituting into the expression for $S(x,y)$ gives
$$ S(x,y) = m\lceil y\rceil + \lfloor y\theta\rfloor + (\lceil y\rceil-y). $$
We now distinguish two cases.
If $\theta=0$, then $x=m$ is an integer and
$$ \lfloor x+1\rfloor=m+1. $$
Since $y\theta=0$,
$$ S(x,y) = m\lceil y\rceil+(\lceil y\rceil-y) = my+(m+1)(\lceil y\rceil-y). $$
Because $\lceil y\rceil-y$ is an integer,
$$ S(x,y) = \left\lfloor my+(m+1)(\lceil y\rceil-y) \right\rfloor. $$
As $x=m$ and $\lfloor x+1\rfloor=m+1$, this becomes
$$ S(x,y) = \left\lfloor xy+\lfloor x+1\rfloor(\lceil y\rceil-y) \right\rfloor. $$
If $0<\theta<1$, then $\lfloor x+1\rfloor=m+1$ and
$$ \lfloor y\theta\rfloor+(\lceil y\rceil-y) = \left\lfloor y\theta+\lceil y\rceil-y \right\rfloor, $$
because $\lceil y\rceil-y$ is an integer. Therefore
$$ S(x,y) = m\lceil y\rceil + \left\lfloor y\theta+\lceil y\rceil-y \right\rfloor. $$
Again using the fact that $m\lceil y\rceil$ is an integer,
\begin{align*}
S(x,y)
&=
\left\lfloor
m\lceil y\rceil+y\theta+\lceil y\rceil-y
\right\rfloor
&= \left\lfloor my+y\theta+(m+1)(\lceil y\rceil-y) \right\rfloor \ &= \left\lfloor xy+\lfloor x+1\rfloor(\lceil y\rceil-y) \right\rfloor. \end{align*} Both cases yield the stated identity. When $y=n$ is a positive integer, $$ \lceil y\rceil-y=n-n=0, $$ hence the formula reduces to $$ \sum_{0\le k<n} \left\lfloor x+\frac{k}{n}\right\rfloor = \lfloor nx\rfloor. $$ Writing the sum explicitly, $$ \lfloor x\rfloor + \left\lfloor x+\frac1n\right\rfloor +\cdots+ \left\lfloor x+\frac{n-1}{n}\right\rfloor = \lfloor nx\rfloor. $$ Therefore $$ \boxed{ \lfloor x\rfloor + \left\lfloor x+\frac1n\right\rfloor +\cdots+ \left\lfloor x+\frac{n-1}{n}\right\rfloor = \lfloor nx\rfloor }. $$ This completes the proof. ∎ ## Verification Take $x=\tfrac12$ and $y=3$. Then $$ \left\lfloor \tfrac12\right\rfloor + \left\lfloor \tfrac12+\tfrac13\right\rfloor + \left\lfloor \tfrac12+\tfrac23\right\rfloor = 0+0+1 = 1. $$ The formula gives $$ \left\lfloor xy+\lfloor x+1\rfloor(\lceil y\rceil-y) \right\rfloor = \left\lfloor \tfrac32+1(3-3) \right\rfloor = 1. $$ Take $x=2$ and $y=\tfrac52$. The admissible integers are $k=0,1,2$, hence $$ \left\lfloor 2\right\rfloor + \left\lfloor 2+\tfrac{2}{5}\right\rfloor + \left\lfloor 2+\tfrac{4}{5}\right\rfloor = 2+2+2 = 6. $$ The formula gives $$ \left\lfloor 2\cdot\tfrac52+\lfloor 3\rfloor \left(3-\tfrac52\right) \right\rfloor = \left\lfloor 5+\tfrac32 \right\rfloor = 6. $$ ## Notes Exercise 37 yields the integer case immediately by taking $m=1$, $n=y$, and replacing $x$ there by $yx$ when $y$ is an integer. Exercise 38 extends this phenomenon to arbitrary positive real $y$ by accounting for the excess $\lceil y\rceil-y$ when $y$ is not integral.