Hermite's Identity

Hermite 恒等式 (Hermite’s Identity)

这是取整函数 (floor function) 理论里最优雅的恒等式之一，署名归于 Charles Hermite。它表面上是个求和公式，但真正的价值在于它给了你一个把”一个大取整”拆成”一串小取整之和”的开关——反过来用，就是把一串看似难缠的取整求和折叠成一个。对你正在打的数论和竞赛路子，这是一件高频趁手的兵器。

---

一、恒等式陈述

对任意实数 $x$ 和任意正整数 $n$：

$\lfloor nx\rfloor ={\sum }_{k=0}^{n-1}\lfloor x+\frac{k}{n}\rfloor =\lfloor x\rfloor +\lfloor x+\frac{1}{n}\rfloor +\lfloor x+\frac{2}{n}\rfloor +\cdots +\lfloor x+\frac{n-1}{n}\rfloor .$

最常见的特例是 $n=2$：

$\lfloor x\rfloor +\lfloor x+\frac{1}{2}\rfloor =\lfloor 2x\rfloor .$

这个 $n=2$ 的版本你几乎一定见过，它单独拿出来就是很多竞赛题的核心。

---

二、证明一：数余数（计数证明，最干净）

这是我最推荐的证法，因为它把”为什么成立”讲得最透。

把 $x$ 拆成整数部分和小数部分：$x=\lfloor x\rfloor +\theta$，其中 $\theta =x\in [0,1)$。因为 $\lfloor x\rfloor$ 是整数，可以直接提出取整号：

$\lfloor x+\frac{k}{n}\rfloor =\lfloor x\rfloor +\lfloor \theta +\frac{k}{n}\rfloor .$

现在关键观察：因为 $\theta <1$ 且 $\frac{k}{n}\le \frac{n-1}{n}<1$，所以 $\theta +\frac{k}{n}\in [0,2)$，于是 $\lfloor \theta +\frac{k}{n}\rfloor$ 只能是 $0$ 或 $1$。而它 $=1$ 当且仅当

$\theta +\frac{k}{n}\ge 1⟺k\ge n(1-\theta ).$

所以求和就是在数有多少个 $k\in \{0,1,\dots ,n-1\}$ 满足 $k\ge n(1-\theta )$。这样的 $k$ 从 $\lceil n(1-\theta )\rceil$ 数到 $n-1$，个数为

$n-\lceil n(1-\theta )\rceil =n-(n-\lfloor n\theta \rfloor )=\lfloor n\theta \rfloor .$

（这里用了整数 $n$ 的等式 $\lceil n-y\rceil =n-\lfloor y\rfloor$。）于是左边：

${\sum }_{k=0}^{n-1}\lfloor x+\frac{k}{n}\rfloor =n\lfloor x\rfloor +\lfloor n\theta \rfloor .$

再看右边：

$\lfloor nx\rfloor =\lfloor n\lfloor x\rfloor +n\theta \rfloor =n\lfloor x\rfloor +\lfloor n\theta \rfloor .$

两边完全相等。$■$

点破本质：整个恒等式其实只在小数部分 $\theta$ 上起作用（整数部分两边各贡献 $n\lfloor x\rfloor$，抵消掉）。而在 $\theta$ 上，左边是”数有多少个平移点越过了整数边界 $1$“，右边 $\lfloor n\theta \rfloor$ 恰好数的是同一件事。取整求和 = 计数，这是取整题最核心的思维转换。

---

三、证明二：周期性（另一种打法，值得会）

第二种证法用的是完全不同的武器——函数的周期性，会它能让你在别处举一反三。

定义误差函数

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

目标是证 $f\equiv 0$。先证它以 $\frac{1}{n}$ 为周期。计算 $f!\left(x+\frac{1}{n}\right)$ 时，求和里的下标整体平移一位：

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

同时 $\lfloor nx+1\rfloor =\lfloor nx\rfloor +1$，两个 $+1$ 相消，得 $f!\left(x+\frac{1}{n}\right)=f(x)$。

既然周期是 $\frac{1}{n}$，只需在长度 $\frac{1}{n}$ 的一段上验证。取 $x\in [0,\frac{1}{n})$：此时 $nx\in [0,1)$ 故 $\lfloor nx\rfloor =0$；而每个 $x+\frac{k}{n}\in [\frac{k}{n},\frac{k+1}{n})\subseteq [0,1)$ 故每个取整都是 $0$。所以在这一段上 $f\equiv 0$，由周期性推出处处为 $0$。$■$

两种证法的对比（这是我想让你带走的东西）：证法一是”静态”的——直接算清结构；证法二是”动态”的——利用”平移一小步、误差不变”把无穷情形压缩到一个小区间。周期性这一招在处理任何”平移不变”的取整/小数问题时都能救命，比证法一的迁移性更广。

---

四、分数部分版本（同一枚硬币的另一面）

把 $\lfloor y\rfloor =y-\{y\}$ 代进去整理，Hermite 恒等式等价地写成小数部分 (fractional part) 的形式：

${\sum }_{k=0}^{n-1}\left\{x+\frac{k}{n}\right\}=\{nx\}+\frac{n-1}{2}.$

这个版本在均匀分布 (equidistribution) 和傅里叶分析里更常用——它告诉你，把 $x$ 沿着 $\frac{1}{n}$ 的格子平移一圈，小数部分的总和只差一个与 $x$ 无关的常数 $\frac{n-1}{2}$。

---

五、推广与血缘关系

这一节是我最想让你看到的，因为它把 Hermite 放进更大的图景里。

① 它是 Bernoulli 多项式乘法定理的”取整版兄弟”。 Bernoulli 多项式满足乘法定理 (multiplication theorem)：

$B_m(nx)=n^{m-1}{\sum }_{k=0}^{n-1}{B}_m!\left(x+\frac{k}{n}\right).$

当 $m=1$ 时 $B_1(y)=y-\frac{1}{2}$，代入两边都得到 $nx-\frac{1}{2}$——这个 $m=1$ 情形是一个恒等式，而它正是 Hermite 恒等式的光滑连续版。换句话说：Hermite 是”锯齿函数 (sawtooth)“世界里的乘法定理，Bernoulli 是”多项式”世界里的同一条定律。同一个’把 $nx$ 拆成 $n$ 个平移点’的机制，在不同函数上的两个化身。

② 它与 Legendre 公式是”取整工具箱”里的同族。 你数论 11 阶段里练过的 Legendre 公式 $v_p(n!)={\sum }_{i\ge 1}\lfloor n/p^i\rfloor$，和 Hermite 一样，本质都是”一个大取整拆成一串取整之和”。区别在于：Legendre 拆的是”数因子 $p$ 的个数”，Hermite 拆的是”平移点越界的个数”。两者都在奖励同一个心法——把 floor 翻译成计数。我把它们看成同一门手艺的两件作品（这是主题上的血缘，不是说一个能直接推出另一个，两者的证明各走各的路）。

---

六、应用：一道漂亮的折叠题

光看恒等式不过瘾，看它怎么”反着用”把难题折叠。

命题：对任意正整数 $n$，$\sum _{k=1}^{\infty }\lfloor \frac{n}{2^k}+\frac{1}{2}\rfloor =n$。（注意 $\lfloor \frac{n}{2^k}+\frac{1}{2}\rfloor$ 就是把 $\frac{n}{2^k}$ 四舍五入到最近整数，所以这题说”把 $n$ 不断除以 $2$、每次四舍五入，加起来正好回到 $n$”。）

证明：把 $n=2$ 的 Hermite 恒等式反解成

$\lfloor x+\frac{1}{2}\rfloor =\lfloor 2x\rfloor -\lfloor x\rfloor .$

取 $x=\frac{n}{2^k}$，则 $2x=\frac{n}{2^{k-1}}$，于是第 $k$ 项变成

$\lfloor \frac{n}{2^k}+\frac{1}{2}\rfloor =\lfloor \frac{n}{2^{k-1}}\rfloor -\lfloor \frac{n}{2^k}\rfloor .$

这是一个裂项 (telescoping)！求和瞬间坍缩：

${\sum }_{k=1}^{\infty }\left(\lfloor \frac{n}{2^{k-1}}\rfloor -\lfloor \frac{n}{2^k}\rfloor \right)=\lfloor \frac{n}{2^0}\rfloor -{\lim }_{k\to \infty }\lfloor \frac{n}{2^k}\rfloor =n-0=n.■$

套路提炼：一个求和项如果长得像 $\lfloor x+\frac{1}{2}\rfloor$，就把它换成 $\lfloor 2x\rfloor -\lfloor x\rfloor$，往往能引爆一个裂项。这正是你偏好的”靠洞察而非套公式”的那类题——恒等式本身是死的，反向使用它制造抵消才是活的。

顺带一个更基础的推论（把 $x=\frac{m}{n}$ 代原式）：

${\sum }_{k=0}^{n-1}\lfloor \frac{m+k}{n}\rfloor =m,$

它是”连续 $n$ 个数除以 $n$ 取整之和恰为 $m$“，在很多计数场合是现成的引理。

---

七、我的评价：它在工具箱里的位置

坦白说，Hermite 恒等式的广度价值中等——它不像归纳法、抽屉原理那样每天都用到。但它的深度价值很高，理由有二：

1. 它是训练”floor = 计数”这一心法的最佳载体。你如果把证法一真正吃透，遇到任何取整求和都会本能地去数越界点，这个反射比记住公式本身值钱得多。
2. 它是通往更高结构的门票。看懂它和 Bernoulli 乘法定理是一回事，你就摸到了解析数论里”分布式 (distribution) 关系”的门槛——这对你往数论/密码学方向走是有回报的伏笔。

对 CMU 15-151 而言，这个恒等式本身不会直接考（那门课取整函数着墨不多），但它训练的严格计数论证正是 15-151 证明部分的地基。放到竞赛里，$n=2$ 版和那道裂项题是必须秒杀的。

---

需要的话，我可以按项目里的考试格式，给你出一套 Hermite 恒等式的证明专题卷（含那种反向使用、裂项、以及推广到 $\lfloor x\rfloor +\lfloor x+\frac{1}{3}\rfloor +\lfloor x+\frac{2}{3}\rfloor$ 的题型），难度按你习惯往竞赛偏；或者做成家族讲义把它和 Legendre、Bernoulli 串成一族。你说方向就行。

---

置信度 (Confidence)：0.97。所有恒等式、两份证明、裂项应用均为标准结果，且我已逐一手工核验（含 $n=2,5$ 的数值抽查）。

关键 caveats：

• 恒等式对任意实数 $x$ 成立（负数、无理数都行），证明一里的拆分 $x=\lfloor x\rfloor +\theta$ 对负 $x$ 依然合法，因为 $\theta =\{x\}$ 始终在 $[0,1)$。
• 第五节里 Hermite 与 Legendre 的关联，我说的是”同族心法”层面的血缘，不是说其中一个能代数地推导出另一个——两者证明路径独立，请勿在正式写作中把它当作蕴含关系。
• Bernoulli 乘法定理只有 $m=1$ 情形对应 Hermite；更高 $m$ 是光滑多项式的性质，与 floor 无直接对应。