Hermite's identity

From Wikipedia, the free encyclopedia

In mathematics, the Hermite's identity states that for every real number x and positive integer n the following holds:

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

[edit] Proof

Write x=\lfloor x\rfloor+\{x\}. There is exactly one k'\in\{1,...,n\} with \lfloor x\rfloor=\left\lfloor x+\frac{k'-1}{n}\right\rfloor\le x<\left\lfloor x+\frac{k'}{n}\right\rfloor=\lfloor x\rfloor+1

\Rightarrow 0=\left\lfloor \{x\}+\frac{k'-1}{n}\right\rfloor\le \{x\}<\left\lfloor \{x\}+\frac{k'}{n}\right\rfloor=1 \, \Rightarrow \, 1-\frac{k'}{n}\le \{x\}<1-\frac{k'-1}{n} \, \Rightarrow \, n-k'\le n\, \{x\}<n-k'+1

Now \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' =n\, \lfloor x\rfloor+\lfloor n\,\{x\}\rfloor=\left\lfloor n\, [x]+n\, \{x\} \right\rfloor=\lfloor nx\rfloor

[edit] See also

Floor function