Hermite's Identity
Hermite's identity is an identity that computes the value of a summation involving floor functions. It is named after Charles Hermite, a French mathematician who did research during the nineteenth century. It is useful in solving equations, proving inequalities, computing sums etc. involving floor functions.
Hermite's Identity
Let \(x\) be a real number, and let \(n\) be a positive integer. Then,
\[\lfloor nx \rfloor = \lfloor x \rfloor + \left \lfloor x + \frac{1}{n} \right \rfloor + \left \lfloor x + \frac{2}{n} \right \rfloor + \dots + \left \lfloor x + \frac{n - 1}{n} \right \rfloor.\]
Notice that there is no restriction on the sign of \(x,\) i.e. it can be positive or negative.
Proof
Before presenting the formal proof, one idea of the proof has to be noted. The key fact here is that \(\lfloor x \rfloor,\left \lfloor x + \frac{1}{n} \right \rfloor,\ldots, \left \lfloor x + \frac{n - 1}{n} \right \rfloor\) can take only two values, namely \(\lfloor x \rfloor\) and \(\lfloor x \rfloor+1\). Showing this is not too hard. Note that
\[\lfloor x \rfloor \le \left \lfloor x + \frac{1}{n} \right \rfloor \le \cdots \le \left \lfloor x + \frac{n - 1}{n} \right \rfloor.\]
Hence, the minimum value of the above terms is \(\lfloor x \rfloor\). The maximum value is
\[\begin{align} \left \lfloor x + \frac{n - 1}{n} \right \rfloor &=\left \lfloor x +1-\frac{1}{n} \right \rfloor\\ &=\left \lfloor \lfloor x \rfloor+ \{x\} +1-\frac{1}{n} \right \rfloor\\ &=\lfloor x \rfloor +1+\left \lfloor \{x\}-\frac{1}{n} \right \rfloor\\ &\le \lfloor x \rfloor +1 \end{align}\]
since \(\left \lfloor \{x\}-\frac{1}{n} \right \rfloor\) is either \(0\) or \(-1\).
This was the key observation and it's going to help us in our proof. As you will see later, the key fact also helps us in problem solving.
The case where \(x\) is an integer is obviously true. So we assume that \(x\) is not an integer. This means \(0<\{x\}<1\). Since
\[\lfloor x \rfloor \le \left \lfloor x + \frac{1}{n} \right \rfloor \le \cdots \le \left \lfloor x + \frac{n - 1}{n} \right \rfloor\le \lfloor x \rfloor+1,\]
there exists an \(i\) such that
\[\lfloor x \rfloor=\left \lfloor x + \frac{1}{n} \right \rfloor=\cdots =\left \lfloor x + \frac{i-1}{n} \right \rfloor\]
and
\[\left \lfloor x + \frac{i}{n} \right \rfloor=\left \lfloor x + \frac{i+1}{n} \right \rfloor=\cdots =\left \lfloor x + \frac{n-1}{n} \right \rfloor=\lfloor x \rfloor+1.\]
Hence
\[\begin{align} \lfloor x \rfloor + \left \lfloor x + \frac{1}{n} \right \rfloor + \left \lfloor x + \frac{2}{n} \right \rfloor + \dots + \left \lfloor x + \frac{n - 1}{n} \right \rfloor &=i\lfloor x \rfloor+(n-i)(\lfloor x \rfloor+1)\\ &=n\lfloor x \rfloor +n-i. \end{align}\]
Now note that \(i\) satisfies
\[\{x\}+\dfrac{i-1}{n}<1\]
and
\[ \{x\}+\dfrac{i}{n}\ge1.\]
Together, these two inequalities give us
\[\dfrac{n-i}{n}\le \{x\}<\dfrac{n-i+1}{n}.\]
Using this, \(n\lfloor x \rfloor +n-i\le n\lfloor x\rfloor+n\{x\}=nx<n\lfloor x\rfloor+n-i+1,\) which implies that \(\lfloor {nx} \rfloor=n\lfloor x \rfloor+n-i\).
Hence
\[\begin{align} \lfloor x \rfloor + \left \lfloor x + \frac{1}{n} \right \rfloor + \left \lfloor x + \frac{2}{n} \right \rfloor + \dots + \left \lfloor x + \frac{n - 1}{n} \right \rfloor &=i\lfloor x \rfloor+(n-i)(\lfloor x \rfloor+1)\\ &=n\lfloor x \rfloor +n-i\\ &=\lfloor nx \rfloor, \end{align}\]
which completes the proof. \(_\square\)
Problem Solving Using Hermite's identity
There are a couple of things to keep in mind when using Hermite's identity:
- \(\lfloor x \rfloor,\left \lfloor x + \frac{1}{n} \right \rfloor,\cdots, \left \lfloor x + \frac{n - 1}{n} \right \rfloor\) can take only two values, namely \(\lfloor x \rfloor\) and \(\lfloor x \rfloor+1\). This idea is very important.
- Substitute \(x=\lfloor x \rfloor+\{x\}\) wherever you can. This idea isn't specific to Hermite's identity, but it is incredibly useful and deserves a mention here.
Now that we are done talking about some main aspects of Hermite's identity, let's solve some problems.
Prove that for any real \(x\), \(\lfloor x \rfloor+\text{round}(x)=\lfloor2x \rfloor,\) where \(\text{round}\) is the function that rounds a number to its nearest integer.
First note that \(\text{round}(x)=\left\lfloor x+\frac12\right\rfloor\). Hence \(\lfloor x \rfloor+\left\lfloor x+\frac12\right\rfloor=\lfloor2x \rfloor\) by Hermite's identiity. \(_\square\)
A good exercise to do at home is to see what Hermite's identity looks like for different values of \(n\). This makes it easier to sometimes spot Hermite's identity.
AIME-1991
Suppose \(r\) is a real number for which \[\]
\[\left\lfloor r + \frac{19}{100} \right\rfloor + \left\lfloor r + \frac{20}{100} \right\rfloor + \left\lfloor r + \frac{21}{100} \right\rfloor + \cdots + \left\lfloor r + \frac{91}{100} \right\rfloor = 546.\]
Find \(\lfloor 100r \rfloor\).
The given sum has exactly \(91-19+1=73\) terms, each of which equals \(\lfloor r \rfloor\) or \(\lfloor r \rfloor+1\). If all of the terms equal \(7\), then the total sum is \(7\cdot 73=521,\) which is less than \(546\). If all of the terms equal \(8\), then the total sum is \(8\cdot 73=581\), which is greater than \(546\). It follows that some of the terms take the value \(7\) while the others take \(8\). This means that \(\lfloor r \rfloor=7\). Suppose the first \(i\) terms take the value \(7\) whie the other \(73-i\) terms take the value \(8\). Then, \(7i+8(73-i)=546\). Solving this, we get \(i=38\). This means that \(\left\lfloor r + \frac{56}{100} \right\rfloor=7\) and \(\left\lfloor r + \frac{57}{100} \right\rfloor=8\). Therefore,
\[\begin{align} \lfloor 100r \rfloor &=\lfloor r \rfloor+\cdots +\left\lfloor r + \frac{56}{100} \right\rfloor+\left\lfloor r + \frac{57}{100} \right\rfloor+\cdots +\left\lfloor r + \frac{99}{100} \right\rfloor\\ &=57\cdot 7+43\cdot 8\\ &=743. \ _\square \end{align}\]
Prove that \(\lfloor 2x \rfloor+\lfloor 2y \rfloor\ge \lfloor x+y \rfloor + \lfloor x \rfloor+\lfloor y \rfloor\).
It must be admitted that there are easier ways to prove this inequality.
Use the fact that \(\lfloor r \rfloor+\left\lfloor r+\frac12\rfloor=\lfloor2r \right\rfloor\) and the given problem reduces to proving the inequality \(\left\lfloor x+\frac12\right\rfloor+\left\lfloor y+\frac12\right\rfloor\ge \lfloor x+y\rfloor\). This can be proven by substituting \(x=\lfloor x \rfloor +\{x\}\) and \(y=\lfloor y \rfloor +\{y\}\) and considering what the fractional parts of \(x\) and \(y\) can be. This part is left to the reader.