调和数是前若干个正整数的倒数之和。对于正整数 n,第 n 个调和数定义为
Hn=k=1∑nk1=1+21+31+⋯+n1.
通常还约定 H0=0。调和数是调和级数的部分和。虽然调和数会无限增大,但增长速度很慢:Hn 近似等于 lnn+γ,其中 γ 为欧拉–马歇罗尼常数。调和数出现在数学分析、数论、组合数学以及随机过程与算法的分析中。
定义与基本性质
最初几个值为
H0=0,H1=1,H2=23,H3=611,H4=1225,H5=60137.
由定义中的求和式可得递推关系
Hn=Hn−1+n1,n≥1.
因此,调和数列严格递增,但相邻两项的增量逐渐趋于零。
每个调和数都是有理数。不过,只要 n>1,Hn 就不是整数。证明如下:设 2r 是不超过 n 的最大的 2 的幂,L 是 1,…,n 的最小公倍数。在分子
LHn=k=1∑nkL,
中,L/2r 为奇数,其余各项均为偶数,因为在不超过 n 的整数中,只有 2r 能被 2r 整除。因此,LHn 为奇数,而 L 为偶数,所以 Hn 不可能是整数。
增长与发散
与 1/x 的积分比较可得
ln(n+1)≤Hn≤1+lnn(n≥1),
其中 ln 表示自然对数。这些不等式既说明 Hn 趋于无穷大,也说明
n→∞limlnnHn=1.
证明发散的一种初等方法,是按相邻的二次幂将各项分组:
H2m=1+j=1∑mk=2j−1+1∑2jk1.
每个内层求和都包含 2j−1 项,且每项至少为 1/2j,因此
H2m≥1+2m.
这个下界会无限增大。这也说明,仅凭各项趋于零,并不能保证无穷级数收敛。
欧拉–马歇罗尼常数
Hn 与 lnn 的差趋于欧拉–马歇罗尼常数:
γ=n→∞lim(Hn−lnn)=0.5772156649….
目前尚不清楚它是有理数还是无理数。
更精确的渐近展开为
Hn=lnn+γ+2n1−12n21+120n41−252n61+O(n−8).
这里的余项用大O记号表示。该展开可由欧拉–麦克劳林公式推出。它是渐近展开,而不是收敛的无穷级数:在固定阶数处截断后,所得近似的精度会随着 n 增大而提高。
下面是一组实用的显式界:
2(n+1)1<Hn−lnn−γ<2n1,n≥1.
恒等式与表示形式
有限和
交换有限二重求和的次序可得
k=1∑nHk=(n+1)Hn−n.
事实上,1/j 这一项出现在 Hj,Hj+1,…,Hn 中,因此它的总贡献为 (n−j+1)/j。
一个相关的恒等式是
k=1∑nkHk=21(Hn2+Hn(2)),Hn(2)=k=1∑nk21.
将 Hn 的平方展开,再把对角项与非对角项分开,即可得到这一恒等式。
调和数还可以表示为交错的二项式和:
Hn=k=1∑n(−1)k+1(kn)k1,
其中 (kn) 是二项式系数。
积分表示
由有限等比级数可得
Hn=∫011−x1−xndx.
当 n 为整数时,x=1 处看似存在的奇点实际上是可去奇点,因为
1−x1−xn=1+x+⋯+xn−1.
逐项积分便得到 1+1/2+⋯+1/n。
生成函数
调和数的普通生成函数为
n=0∑∞Hnxn=−1−xln(1−x),∣x∣<1.
例如,交换两个绝对收敛求和的次序即可推出此式:
n=1∑∞k=1∑nkxn=1−x1k=1∑∞kxk.
借助生成函数,许多涉及调和数的恒等式都可以转化为幂级数的代数运算。
广义调和数
s 阶广义调和数定义为
Hn(s)=k=1∑nks1.
当 s 为复数时,约定 k−s=exp(−slnk)。普通调和数对应于 s=1 的情形。
对于实数 s>1,这些和随着 n 增大而收敛:
n→∞limHn(s)=ζ(s),
其中 ζ 为黎曼ζ函数。特别地,
n→∞limHn(2)=6π2.
更一般地,当复数 s 满足 Re(s)>1 时,这些和也收敛。对于实数 s≤1,这些和则发散至正无穷大。
当 s=0 时,Hn(0)=n。负整数阶对应于正整数幂之和,例如
Hn(−1)=k=1∑nk=2n(n+1).
向非整数下标的推广
双伽马函数 ψ 是伽马函数的对数导数,满足
Hn=ψ(n+1)+γ.
由此可作出标准推广:
Hz=ψ(z+1)+γ.
这一定义给出了一个复变量亚纯函数,其极点位于负整数处,并且在等式两边均有定义的地方,仍满足递推关系
Hz−Hz−1=z1
。仅要求在非负整数处取值一致,并不能唯一确定推广方式;双伽马函数公式指定了通常采用的那一种。
在概率论与算法中的应用
当一个过程由连续多个阶段构成,且各阶段的等待时间或成功概率涉及倒数关系时,往往会出现调和数。
集齐优惠券
在集齐优惠券问题中,每次独立抽取都会等概率地得到 n 种优惠券中的一种。已经出现 k 种不同的优惠券后,下一次抽到新种类的概率为 (n−k)/n。因此,获得下一种新优惠券所需抽取次数的期望为 n/(n−k)。
将各阶段的期望相加可得
E[T]=k=0∑n−1n−kn=nHn.
因此,集齐所有种类所需等待时间的期望值按 nlnn 的速度增长。
随机序列中的纪录
设 X1,…,Xn 是来自同一连续概率分布的独立观测值。如果第 k 个观测值大于它之前的所有观测值,就称其创下新高纪录。由对称性,前 k 个观测值中的每一个都有相同的概率成为其中的最大值,因此 Xk 创下纪录的概率为 1/k。再由期望的线性性质可得
E[number of record highs]=Hn.
快速排序
对 n 个互不相同的键值执行随机化快速排序,若每次都从当前子数组中均匀随机选取枢轴,并在划分时将其余每个键值与枢轴各比较一次,则比较次数的期望为
E[Cn]=2(n+1)Hn−4n.
由于 Hn 按对数速度增长,上式的主导项为 2nlnn。这是对随机枢轴选择取平均得到的结果,并非每次执行都满足的界;极不均衡的划分可能使比较次数达到平方量级。
数值计算
直接计算需要进行 n 次求倒数运算和加法。当 n 很大,且只需要近似值而非精确分数时,使用渐近展开通常更高效。
在浮点运算中,将越来越小的项加到不断增大的总和上,可能导致低位信息丢失。从较小项向较大项依次求和,或采用补偿求和,可以减少这种舍入误差的累积。精确的有理数运算可以避免舍入,但可能需要处理很大的整数分子和分母。