title: Hermite's identity
text: # Hermite's identity
  
  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:
  
      $\sum _{k=0}^{n-1}\left\lfloor x+{\frac {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+{\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 $\lfloor x\rfloor$ from inside the floor operations on the left and right sides of this inequality, it may be rewritten as
  
      $0=\left\lfloor \{x\}+{\frac {k'-1}{n}}\right\rfloor \leq \{x\}<\left\lfloor \{x\}+{\frac {k'}{n}}\right\rfloor =1.$
  
  Therefore,
  
      $1-{\frac {k'}{n}}\leq \{x\}<1-{\frac {k'-1}{n}},$
  
  and multiplying both sides by $n$ gives
  
      $n-k'\leq n\,\{x\}<n-k'+1.$
  
  Now if the summation from Hermite's identity is split into two parts at index $k'$, it becomes
  
      ${\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
  
  Consider the function
  
      $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$ for all real $x$. But then we find,
  
      $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 $\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$.
  
  