Hermite's identity

In mathematics, Hermite's identity, named after Charles Hermite, gives the value of a summation involving the floor function. It states that for every real number x and for every positive integer n the following identity holds:[1][2]

${\displaystyle \sum _{k=0}^{n-1}\left\lfloor x+{\frac {k}{n}}\right\rfloor =\lfloor nx\rfloor .}$

Proof

Split ${\displaystyle x}$ into its integer part and fractional part, ${\displaystyle x=\lfloor x\rfloor +\{x\}}$. There is exactly one ${\displaystyle k'\in \{1,\ldots ,n\}}$ with

${\displaystyle \lfloor x\rfloor =\left\lfloor x+{\frac {k'-1}{n}}\right\rfloor \leq x<\left\lfloor x+{\frac {k'}{n}}\right\rfloor =\lfloor x\rfloor +1.}$

By subtracting the same integer ${\displaystyle \lfloor x\rfloor }$ from inside the floor operations on the left and right sides of this inequality, it may be rewritten as

${\displaystyle 0=\left\lfloor \{x\}+{\frac {k'-1}{n}}\right\rfloor \leq \{x\}<\left\lfloor \{x\}+{\frac {k'}{n}}\right\rfloor =1.}$

Therefore,

${\displaystyle 1-{\frac {k'}{n}}\leq \{x\}<1-{\frac {k'-1}{n}},}$

and multiplying both sides by ${\displaystyle n}$ gives

${\displaystyle n-k'\leq n\,\{x\}<n-k'+1.}$

Now if the summation from Hermite's identity is split into two parts at index ${\displaystyle k'}$, it becomes

${\displaystyle {\begin{aligned}\sum _{k=0}^{n-1}\left\lfloor x+{\frac {k}{n}}\right\rfloor &=\sum _{k=0}^{k'-1}\lfloor x\rfloor +\sum _{k=k'}^{n-1}(\lfloor x\rfloor +1)=n\,\lfloor x\rfloor +n-k'\\[8pt]&=n\,\lfloor x\rfloor +\lfloor n\,\{x\}\rfloor =\left\lfloor n\,\lfloor x\rfloor +n\,\{x\}\right\rfloor =\lfloor nx\rfloor .\end{aligned}}}$

Alternate Proof

Consider the function

${\displaystyle f(x)=\lfloor x\rfloor +\left\lfloor x+{\frac {1}{n}}\right\rfloor +\ldots +\left\lfloor x+{\frac {n-1}{n}}\right\rfloor -\lfloor nx\rfloor }$

Then the identity is clearly equivalent to the statement ${\displaystyle f(x)=0}$ for all real ${\displaystyle x}$. But then we find,

${\displaystyle f\left(x+{\frac {1}{n}}\right)=\left\lfloor x+{\frac {1}{n}}\right\rfloor +\left\lfloor x+{\frac {2}{n}}\right\rfloor +\ldots +\left\lfloor x+1\right\rfloor -\lfloor nx+1\rfloor =f(x)}$

Where in the last equality we use the fact that ${\displaystyle \lfloor x+p\rfloor =\lfloor x\rfloor +p}$ for all integers ${\displaystyle p}$. But then ${\displaystyle f}$ has period ${\displaystyle 1/n}$. It then suffices to prove that ${\displaystyle f(x)=0}$ for all ${\displaystyle x\in [0,1/n)}$. But in this case, the integral part of each summand in ${\displaystyle f}$ is equal to 0. We deduce that the function is indeed 0 for all real inputs ${\displaystyle x}$.

References

1. Savchev, Svetoslav; Andreescu, Titu (2003), "12 Hermite's Identity", Mathematical Miniatures, New Mathematical Library, 43, Mathematical Association of America, pp. 41–44, ISBN 9780883856451.
2. Matsuoka, Yoshio (1964), "Classroom Notes: On a Proof of Hermite's Identity", The American Mathematical Monthly, 71 (10): 1115, doi:10.2307/2311413, MR 1533020.