Hermite's identity

Short description: Gives the value of a summation involving the floor function

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:

[math]\displaystyle{ \sum_{k=0}^{n-1}\left\lfloor x+\frac{k}{n}\right\rfloor=\lfloor nx\rfloor . }[/math]

Proofs

Proof by algebraic manipulation

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

[math]\displaystyle{ \lfloor x\rfloor=\left\lfloor x+\frac{k'-1}{n}\right\rfloor\le x\lt \left\lfloor x+\frac{k'}{n}\right\rfloor=\lfloor x\rfloor+1. }[/math]

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

[math]\displaystyle{ 0=\left\lfloor \{x\}+\frac{k'-1}{n}\right\rfloor\le \{x\}\lt \left\lfloor \{x\}+\frac{k'}{n}\right\rfloor=1. }[/math]

Therefore,

[math]\displaystyle{ 1-\frac{k'}{n}\le \{x\}\lt 1-\frac{k'-1}{n} , }[/math]

and multiplying both sides by [math]\displaystyle{ n }[/math] gives

[math]\displaystyle{ n-k'\le n\, \{x\}\lt n-k'+1. }[/math]

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

[math]\displaystyle{ \begin{align} \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{align} }[/math]

Proof using functions

Consider the function

[math]\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 }[/math]

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

[math]\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) }[/math]

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