Hermite's identity

Template:Short description Template:Distinguish In mathematics, identity of Hermite, 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:

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

Proofs

Proof by algebraic manipulation

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

$\lfloor x\rfloor =\lfloor x+\frac{k^{\prime }-1}{n}\rfloor \le x<\lfloor x+\frac{k^{\prime }}{n}\rfloor =\lfloor x\rfloor +1.$

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

$0=\lfloor \{x\}+\frac{k^{\prime }-1}{n}\rfloor \le \{x\}<\lfloor \{x\}+\frac{k^{\prime }}{n}\rfloor =1.$

Therefore,

$1-\frac{k^{\prime }}{n}\le \{x\}<1-\frac{k^{\prime }-1}{n},$

and multiplying both sides by $n$ gives

$n-k^{\prime }\le n\{x\}<n-k^{\prime }+1.$

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

$\begin{array}{cc}\sum _{k=0}^{n-1}\lfloor x+\frac{k}{n}\rfloor & =\sum _{k=0}^{k^{\prime }-1}\lfloor x\rfloor +\sum _{k=k^{\prime }}^{n-1}(\lfloor x\rfloor +1)=n\lfloor x\rfloor +n-k^{\prime }\\ & =n\lfloor x\rfloor +\lfloor n\{x\}\rfloor =\lfloor n\lfloor x\rfloor +n\{x\}\rfloor =\lfloor nx\rfloor .\end{array}$

Proof using functions

Consider the function

$f(x)=\lfloor x\rfloor +\lfloor x+\frac{1}{n}\rfloor +\dots +\lfloor x+\frac{n-1}{n}\rfloor -\lfloor nx\rfloor$

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

$f(x+\frac{1}{n})=\lfloor x+\frac{1}{n}\rfloor +\lfloor x+\frac{2}{n}\rfloor +\dots +\lfloor x+1\rfloor -\lfloor nx+1\rfloor =f(x)$

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