Theorem 3.2.1. Hermite’s Identity.
For any real \(x\) and positive integer \(n\text{,}\)
\begin{equation}
\sum_{0 \leq k \leq n-1} \left\lfloor x + \frac{k}{n} \right\rfloor
= \lfloor n x \rfloor\tag{3.2.1}
\end{equation}
Section 3.2 Hermite’s Identity
Example 3.2.2.
If \(n=1\) the statement says:
\begin{equation*}
\sum_{k=0} \left\lfloor x + \frac{k}{1} \right\rfloor
= \lfloor x + 0 \rfloor
= \lfloor 1 x \rfloor\text{.}
\end{equation*}
If \(n=2\) the sum is:
\begin{equation*}
\sum_{0 \leq k \leq 1} \left\lfloor x + \frac{k}{n} \right\rfloor
= \lfloor x \rfloor + \left\lfloor x + \frac{1}{2} \right\rfloor\text{.}
\end{equation*}
Say \(\lfloor x \rfloor = m\text{.}\) If \(m \leq x \lt m + \frac{1}{2}\) then
\begin{equation*}
\lfloor x \rfloor + \left\lfloor x + \frac{1}{2} \right\rfloor
= m + m = 2m
\end{equation*}
and
\begin{equation*}
\lfloor 2x \rfloor = 2m
\end{equation*}
because \(2m \leq 2x \lt 2m+1\text{.}\) Otherwise if \(m + \frac{1}{2} \leq x \lt m+1\) then
\begin{equation*}
\lfloor x \rfloor + \left\lfloor x + \frac{1}{2} \right\rfloor
= m + (m+1) = 2m+1 = \lfloor 2x \rfloor
\end{equation*}
because \(2m+1 \leq 2x \lt 2m+2\text{.}\)The textbook gives several generalizations of this theorem, for example summing \(0 \leq k \leq m-1\) where \(m\) can be a different integer than \(n\text{.}\) For class we’ll just give a direct proof of Hermite’s identity rather than one of the generalizations.
Proof.
Let \(m\) be the integer such that
\begin{equation*}
\frac{m}{n} \leq x \lt \frac{m+1}{n} \text{,}
\end{equation*}
in other words \(m = \lfloor n x \rfloor\text{.}\) Write \(m = q n + r\) where \(0 \leq r \lt n\text{.}\) Observe that \(q + \frac{r}{n} \leq x \lt q + \frac{r+1}{n}\text{.}\) In particular \(\lfloor x \rfloor = q\text{.}\)
For \(0 \leq k \leq n - r - 1\) we have
\begin{align*}
q \amp \leq x \\
\amp \leq x + \frac{k}{n} \\
\amp \lt \frac{m+1}{n} + \frac{k}{n} \\
\amp \leq \frac{q n + r + 1 + (n-r-1)}{n} \\
\amp = q + 1 \text{.}
\end{align*}
That is,
\begin{equation*}
q \leq x + \frac{k}{n} \lt q+1 \text{.}
\end{equation*}
Then \(\left\lfloor x + \frac{k}{n} \right\rfloor = q \text{.}\)
For \(n-r \leq k \leq n-1\) we have
\begin{align*}
q+1 \amp = q + \frac{r}{n} + \frac{n-r}{n} \\
\amp \leq x + \frac{k}{n} \\
\amp \lt \frac{m+1}{n} + \frac{k}{n} \\
\amp \leq \frac{q n + r + n-1}{n} \\
\amp \leq \frac{q n + n + n}{n} \\
\amp = q + 2 \text{.}
\end{align*}
So \(q+1 \leq x + \frac{k}{n} \lt q+2\text{.}\) Therefore \(\left\lfloor x + \frac{k}{n} \right\rfloor = q+1\text{.}\)
Now the sum in Hermite’s identity has \(n-r\) terms that are equal to \(q\text{,}\) and \(r\) terms that are equal to \(q+1\text{.}\) So the sum is equal to \((n-r)q + r(q+1)\text{,}\) which is equal to \(nq+r = m = \lfloor n x \rfloor\text{.}\)
