Hermite's identity explained

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]}

\sum ^{n -1} _{k =0} \left\lfloor x + (k)/(n) \right\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'\in\{ 1 ,\ldots,n\} with \lfloor x\rfloor = \left\lfloor x + (k' -1)/(n) \right\rfloor\le x<\left\lfloor x + (k')/(n) \right\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 as0= \left\lfloor \{x\} + (k' -1)/(n) \right\rfloor\le \{x\}<\left\lfloor \{x\} + (k')/(n) \right\rfloor =1 .

Therefore,

1- (k')/(n) \le \{x\}< 1- (k' -1)/(n) ,

and multiplying both sides by

n givesn - k'\le n \{x\}<n - k' +1 .

Now if the summation from Hermite's identity is split into two parts at index

k' , it becomes\begin{align} \sum ^{n -1} _{k =0} \left\lfloor x + (k)/(n) \right\rfloor & = \sum ^{k' -1} _{k =0} \lfloor x\rfloor + \sum ^{n -1} _{k = k'} (\lfloor x\rfloor +1 ) = n \lfloor x\rfloor + n - k' \\[ 8 pt] & = n \lfloor x\rfloor + \lfloor n\{x\}\rfloor = \left\lfloor n \lfloor x\rfloor + n \{x\} \right\rfloor = \lfloor nx\rfloor. \end{align}

Proof using functions

Consider the function

f(x) = \lfloor x \rfloor + \left\lfloor x + (1)/(n) \right\rfloor + \ldots + \left\lfloor x + (n -1)/(n) \right\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\left(x + (1)/(n) \right) = \left\lfloor x + (1)/(n) \right\rfloor + \left\lfloor x + (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

\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 .

Notes and References

1. .
2. .