Section 3.3 Applications of Hermite’s Identity
Here are a few examples illustrating uses of Hermite’s identity.
Proposition 3.3.1.
Let \(n \in \bbN\text{.}\) Then
\begin{equation}
n = \left\lfloor \frac{n+1}{2} \right\rfloor
+ \left\lfloor \frac{n+2}{2^2} \right\rfloor
+ \left\lfloor \frac{n+2^2}{2^3} \right\rfloor
+ \left\lfloor \frac{n+2^3}{2^4} \right\rfloor
+ \dotsb\text{.}\tag{3.3.1}
\end{equation}
Proof.
For sufficiently large \(k\text{,}\) observe that
\begin{equation*}
\left\lfloor \frac{n+2^k}{2^{k+1}} \right\rfloor
= \left\lfloor \frac{1}{2} + \frac{n}{2^{k+1}} \right\rfloor
= 0
\end{equation*}
(as soon as \(n/2^{k+1} \lt 1/2\)). So the sum is actually a finite sum.
Now we use Hermite’s identity: From
\begin{equation*}
\lfloor x \rfloor + \left\lfloor x + \frac{1}{2} \right\rfloor = \lfloor 2x \rfloor
\end{equation*}
we get
\begin{equation*}
\left\lfloor x + \frac{1}{2} \right\rfloor = \lfloor 2x \rfloor - \lfloor x \rfloor\text{.}
\end{equation*}
Applying this to the right hand side of the equation, we have
\begin{align*}
\left\lfloor \frac{n+1}{2} \right\rfloor
\amp
+ \left\lfloor \frac{n+2}{2^2} \right\rfloor
+ \left\lfloor \frac{n+2^2}{2^3} \right\rfloor
+ \left\lfloor \frac{n+2^3}{2^4} \right\rfloor
+ \dotsb\\
\amp = \left\lfloor \frac{1}{2} + \frac{n}{2} \right\rfloor
+ \left\lfloor \frac{1}{2} + \frac{n}{2^2} \right\rfloor
+ \left\lfloor \frac{1}{2} + \frac{n}{2^3} \right\rfloor
+ \dotsb\\
\amp = \left( \lfloor n \rfloor - \left\lfloor \frac{n}{2} \right\rfloor \right)
+ \left( \left\lfloor \frac{n}{2} \right\rfloor - \left\lfloor \frac{n}{2^2} \right\rfloor \right)
+ \left( \left\lfloor \frac{n}{2^2} \right\rfloor - \left\lfloor \frac{n}{2^3} \right\rfloor \right)
+ \dotsb
\end{align*}
and the sum telescopes to \(\lfloor n \rfloor\) which is equal to \(n\text{.}\)
Proposition 3.3.2.
Let \(a\) and \(b\) be relatively prime positive integers. Then
\begin{equation}
\sum_{k=1}^{b-1} \left\lfloor \frac{k a}{b} \right\rfloor = \frac{(a-1)(b-1)}{2}\text{.}\tag{3.3.2}
\end{equation}
Proof (given in textbook).
Observe that the sum is unchanged if \(k\) is replaced by \(b-k\text{.}\) So,
\begin{align*}
\sum_{k=1}^{b-1} \left\lfloor \frac{k a}{b} \right\rfloor
\amp = \sum_{k=1}^{b-1} \left\lfloor \frac{(b-k) a}{b} \right\rfloor\\
\amp = \sum_{k=1}^{b-1} \left\lfloor a - \frac{k a}{b} \right\rfloor\\
\amp = (b-1)a + \sum_{k=1}^{b-1} \left\lfloor \frac{ - k a}{b} \right\rfloor\text{.}
\end{align*}
Now, we have seen that \(\lfloor -x \rfloor = - \lceil x \rceil\text{.}\) If \(x\) is not an integer, then \(\lceil x \rceil = \lfloor x \rfloor + 1\text{.}\) In this case, \(\lfloor -x \rfloor = - \lfloor x \rfloor - 1\text{.}\) In our sum, for \(1 \leq k \leq b-1\text{,}\) \(\frac{k a}{b}\) is not an integer, by our assumption that \(a\) and \(b\) are relatively prime (why is this?). Therefore
\begin{align*}
\sum_{k=1}^{b-1} \left\lfloor \frac{k a}{b} \right\rfloor
\amp = (b-1)a + \sum_{k=1}^{b-1} \left\lfloor \frac{ - k a}{b} \right\rfloor\\
\amp = (b-1)a + \sum_{k=1}^{b-1} - \left\lfloor \frac{k a}{b} \right\rfloor - 1\\
\amp = (b-1)a - \sum_{k=1}^{b-1} \left\lfloor \frac{k a}{b} \right\rfloor - (b-1)\\
\amp = (a-1)(b-1) - \sum_{k=1}^{b-1} \left\lfloor \frac{k a}{b} \right\rfloor\text{.}
\end{align*}
Finally, solving for the sum gives the result.
Proof (using Hermite’s identity and lattice point counting).
First, observe that
\begin{equation*}
\left\lfloor \frac{k a}{b} \right\rfloor
= \sum_{j=0}^{a-1} \left\lfloor \frac{k}{b} + \frac{j}{a} \right\rfloor
\end{equation*}
by Hermite’s identity. So the sum is
\begin{equation}
\sum_{k=0}^{b-1} \left\lfloor \frac{k a}{b} \right\rfloor
= \sum_{k=0}^{b-1} \sum_{j=0}^{a-1} \left\lfloor \frac{k}{b} + \frac{j}{a} \right\rfloor\text{.}\tag{3.3.3}
\end{equation}
Next, observe that \(0 \leq \frac{k}{b}, \frac{j}{a} \lt 1\) for \(0 \leq k \leq b-1\) and \(0 \leq j \leq a-1\text{.}\) Therefore
\begin{equation*}
0 \leq \frac{k}{b} + \frac{j}{a} \lt 2\text{.}
\end{equation*}
This means that the floor of the sum of fractions is either \(0\) or \(1\text{.}\) So our sum is equal to the number of pairs \((j,k)\) such that \(\frac{k}{b} + \frac{j}{a} \geq 1\text{.}\)
Each pair \((j,k)\) with \(0 \leq j \leq a-1\) and \(0 \leq k \leq b-1\) corresponds to a lattice point in the rectangle \([0,a) \times [0,b)\text{.}\) The pairs \((j,k)\) such that \(\frac{k}{b} + \frac{j}{a} \geq 1\) correspond to lattice points that lie on or above the line defined by \(\frac{y}{b} + \frac{x}{a} = 1\text{.}\) This is the line that cuts the rectangle diagonally from \((0,b)\) in the upper left to \((a,0)\) in the lower right.
First, observe that no lattice points lie on the interior of this diagonal line. That is, the only lattice points on this diagonal line, in the segment where it intersects the rectangle, are the endpoints, the corners of the rectangle. This is because of the hypothesis that \(a\) and \(b\) are relatively prime. If there were a lattice point \((x,y)\) on the line, then we could write the slope of the line in two ways, as
\begin{equation*}
-\frac{b}{a} = -\frac{b-y}{x}\text{.}
\end{equation*}
But the hypothesis means that \(b/a\) is already in lowest terms.
By symmetry, exactly half of the lattice points in the closed rectangle \([0,a] \times [0,b]\) (other than the two corner endpoints of the diagonal) lie above the line, and exactly half lie below. There are \((a+1)(b+1)\) lattice points in this closed rectangle. So \((ab+a+b-1)/2\) of them lie above the diagonal.
However we are only counting lattice points in the half-open rectangle \([0,a) \times [0,b)\text{.}\) So we have to take away the lattice points on the north and east (upper and right) sides of the rectangle. There are \(a+b-1\) of these (why?). Therefore the number of lattice points, giving us the sum we are seeking, is
\begin{equation*}
\frac{ab+a+b-1}{2} - (a+b-1) = \frac{ab-a-b+1}{2} = \frac{(a-1)(b-1)}{2}
\end{equation*}
as claimed.
