זהות הרמיט

זהות הרמיט (באנגלית: Hermite's identity) היא משפט בתורת המספרים, הנקראת על שם המתמטיקאי הצרפתי שארל הרמיט. היא מספקת תובנות חשובות לגבי תכונות של מספרים שלמים ושימושיה באלגברה ובאנליזה. היא משמשת בעיקר להוכחת התכונות של פונקציות מחזוריות ובבניית אלגוריתמים לחישובים בתורת המספרים.

הזהות קובעת כי לכל $n\geq 1$ שלם ולכל $x$ ממשי מתקיים

$\sum _{k\,=\,0}^{n-1}\left\lfloor x+{\frac {k}{n}}\right\rfloor =\lfloor nx\rfloor$

כאשר $\lfloor x\rfloor$ פונקציית הערך השלם.

הוכחה

באמצעות אלגברה

נכתוב $x=\lfloor x\rfloor +\{x\}$, כאשר $\lfloor x\rfloor$ הערך השלם ו-$\{x\}$ החלק השברי. ראשית ברור כי מתקיים

$\lfloor x\rfloor \leq \left\lfloor x+{\frac {1}{n}}\right\rfloor \leq \cdots \leq \left\lfloor x+{\frac {n-1}{n}}\right\rfloor \leq \lfloor x\rfloor +1$

קיים בדיוק איבר אחד $m\in \{1,\ldots ,n\}$ עבורו

$\lfloor x\rfloor =\left\lfloor x+{\frac {1}{n}}\right\rfloor =\cdots =\left\lfloor x+{\frac {m-1}{n}}\right\rfloor \leq x<\left\lfloor x+{\frac {m}{n}}\right\rfloor =\left\lfloor x+{\frac {m+1}{n}}\right\rfloor =\cdots =\lfloor x\rfloor +1$

נחסר מהאי-שוויון את הביטוי $\lfloor x\rfloor$, ועל פי תכונות הערך השלם נקבל

${\begin{aligned}0=\left\lfloor \{x\}+{\frac {m-1}{n}}\right\rfloor \leq \{x\}<\left\lfloor \{x\}+{\frac {m}{n}}\right\rfloor =1\\\{x\}+{\frac {m-1}{n}}<1\leq \{x\}+{\frac {m}{n}}\\n-m\leq n\{x\}<n-m+1\\\lfloor n\{x\}\rfloor =n-m\end{aligned}}$

נחלק את הסכום המבוקש לשני סכומים מתאימים, ונקבל

${\begin{aligned}\sum _{k\,=\,0}^{n-1}\left\lfloor x+{\frac {k}{n}}\right\rfloor &=\sum _{k\,=\,0}^{m-1}\left\lfloor x+{\frac {k}{n}}\right\rfloor +\sum _{k\,=\,m}^{n-1}\left\lfloor x+{\frac {k}{n}}\right\rfloor \\&=\sum _{k\,=\,0}^{m-1}\lfloor x\rfloor +\sum _{k\,=\,m}^{n-1}\left(\lfloor x\rfloor +1\right)\\&=n\lfloor x\rfloor +n-m\\&=n\lfloor x\rfloor +\lfloor n\{x\}\rfloor \\&={\Big \lfloor }n\lfloor x\rfloor +n\{x\}{\Big \rfloor }\\&=\lfloor nx\rfloor \end{aligned}}$

באמצעות פונקציות

נגדיר פונקציה $f(x)=\sum _{k\,=\,0}^{n-1}\left\lfloor x+{\frac {k}{n}}\right\rfloor -\lfloor nx\rfloor$. מכאן נקבל

${\begin{aligned}f\left(x+{\frac {1}{n}}\right)&=\sum _{k\,=\,1}^{n}\left\lfloor x+{\frac {k}{n}}\right\rfloor -\lfloor nx+1\rfloor \\&=\sum _{k\,=\,1}^{n-1}\left\lfloor x+{\frac {k}{n}}\right\rfloor +\lfloor x+1\rfloor -\lfloor nx+1\rfloor \\&=\sum _{k\,=\,1}^{n-1}\left\lfloor x+{\frac {k}{n}}\right\rfloor +(\lfloor x\rfloor +1)-(\lfloor nx\rfloor +1)\\&=\sum _{k\,=\,0}^{n-1}\left\lfloor x+{\frac {k}{n}}\right\rfloor -\lfloor nx\rfloor \\&=f(x)\end{aligned}}$

כלומר לפונקציה מחזור בגודל ${\tfrac {1}{n}}$, ולכן די להראות כי $f(x)=0$ לכל $x\in {\bigl [}0,{\tfrac {1}{n}}{\bigr )}$:

$\forall \,0\leq x<{\frac {1}{n}}:\quad {\begin{cases}\forall \,0\leq k\leq n-1:\quad 0\leq x+{\dfrac {k}{n}}<{\dfrac {1}{n}}+{\dfrac {n-1}{n}}=1\iff \left\lfloor x+{\dfrac {k}{n}}\right\rfloor =0\\0\leq nx<1\iff \left\lfloor nx\right\rfloor =0\end{cases}}$

קישורים חיצוניים

• FRANZ LEMMERMEYER, Hermite's identity, Heidelberg University