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:[ 1] [ 2]
∑ k = 0 n − 1 ⌊ x + k n ⌋ = ⌊ n x ⌋ . {\displaystyle \sum _{k=0}^{n-1}\left\lfloor x+{\frac {k}{n}}\right\rfloor =\lfloor nx\rfloor .} Proof by algebraic manipulation [ edit ] Split x {\displaystyle x} into its integer part and fractional part , x = ⌊ x ⌋ + { x } {\displaystyle x=\lfloor x\rfloor +\{x\}} . There is exactly one k ′ ∈ { 1 , … , n } {\displaystyle k'\in \{1,\ldots ,n\}} with
⌊ x ⌋ = ⌊ x + k ′ − 1 n ⌋ ≤ x < ⌊ x + k ′ n ⌋ = ⌊ x ⌋ + 1. {\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 ⌊ x ⌋ {\displaystyle \lfloor x\rfloor } from inside the floor operations on the left and right sides of this inequality, it may be rewritten as
0 = ⌊ { x } + k ′ − 1 n ⌋ ≤ { x } < ⌊ { x } + k ′ n ⌋ = 1. {\displaystyle 0=\left\lfloor \{x\}+{\frac {k'-1}{n}}\right\rfloor \leq \{x\}<\left\lfloor \{x\}+{\frac {k'}{n}}\right\rfloor =1.} Therefore,
1 − k ′ n ≤ { x } < 1 − k ′ − 1 n , {\displaystyle 1-{\frac {k'}{n}}\leq \{x\}<1-{\frac {k'-1}{n}},} and multiplying both sides by n {\displaystyle n} gives
n − k ′ ≤ n { x } < n − k ′ + 1. {\displaystyle n-k'\leq n\,\{x\}<n-k'+1.} Now if the summation from Hermite's identity is split into two parts at index k ′ {\displaystyle k'} , it becomes
∑ k = 0 n − 1 ⌊ x + k n ⌋ = ∑ k = 0 k ′ − 1 ⌊ x ⌋ + ∑ k = k ′ n − 1 ( ⌊ x ⌋ + 1 ) = n ⌊ x ⌋ + n − k ′ = n ⌊ x ⌋ + ⌊ n { x } ⌋ = ⌊ n ⌊ x ⌋ + n { x } ⌋ = ⌊ n x ⌋ . {\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}}} Proof using functions [ edit ] Consider the function
f ( x ) = ⌊ x ⌋ + ⌊ x + 1 n ⌋ + … + ⌊ x + n − 1 n ⌋ − ⌊ n x ⌋ {\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 f ( x ) = 0 {\displaystyle f(x)=0} for all real x {\displaystyle x} . But then we find,
f ( x + 1 n ) = ⌊ x + 1 n ⌋ + ⌊ x + 2 n ⌋ + … + ⌊ x + 1 ⌋ − ⌊ n x + 1 ⌋ = f ( x ) {\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 ⌊ x + p ⌋ = ⌊ x ⌋ + p {\displaystyle \lfloor x+p\rfloor =\lfloor x\rfloor +p} for all integers p {\displaystyle p} . But then f {\displaystyle f} has period 1 / n {\displaystyle 1/n} . It then suffices to prove that f ( x ) = 0 {\displaystyle f(x)=0} for all x ∈ [ 0 , 1 / n ) {\displaystyle x\in [0,1/n)} . But in this case, the integral part of each summand in f {\displaystyle f} is equal to 0. We deduce that the function is indeed 0 for all real inputs x {\displaystyle x} .
^ Savchev, Svetoslav; Andreescu, Titu (2003), "12 Hermite's Identity", Mathematical Miniatures , New Mathematical Library, vol. 43, Mathematical Association of America , pp. 41–44, ISBN 9780883856451 . ^ Matsuoka, Yoshio (1964), "Classroom Notes: On a Proof of Hermite's Identity", The American Mathematical Monthly , 71 (10): 1115, doi :10.2307/2311413 , JSTOR 2311413 , MR 1533020 .