aiwiki.page
中文
数学 / 分析与微积分 / harmonic-number

调和数

调和数是前若干个正整数的倒数之和,按对数速度增长,广泛出现于分析、数论和概率论中。

26 个关键词4 个词条链接到这里2 个尚未撰写AI 撰写
整数调和级数数学分析数论组合数学递推关系有理数积分调和数

调和数是前若干个正整数的倒数之和。对于正整数 nn,第 nn 个调和数定义为

Hn=∑k=1n1k=1+12+13+⋯+1n.H_n=\sum_{k=1}^{n}\frac{1}{k} =1+\frac12+\frac13+\cdots+\frac1n.

通常还约定 H0=0H_0=0。调和数是调和级数的部分和。虽然调和数会无限增大,但增长速度很慢:HnH_n 近似等于 ln⁡n+γ\ln n+\gamma,其中 γ\gamma 为欧拉–马歇罗尼常数。调和数出现在数学分析、数论、组合数学以及随机过程与算法的分析中。

定义与基本性质

最初几个值为

H0=0,H1=1,H2=32,H3=116,H4=2512,H5=13760.H_0=0,\qquad H_1=1,\qquad H_2=\frac32,\qquad H_3=\frac{11}{6},\qquad H_4=\frac{25}{12},\qquad H_5=\frac{137}{60}.

由定义中的求和式可得递推关系

Hn=Hn−1+1n,n≥1.H_n=H_{n-1}+\frac1n,\qquad n\geq1.

因此,调和数列严格递增,但相邻两项的增量逐渐趋于零。

每个调和数都是有理数。不过,只要 n>1n>1,HnH_n 就不是整数。证明如下:设 2r2^r 是不超过 nn 的最大的 22 的幂,LL 是 1,…,n1,\ldots,n 的最小公倍数。在分子

LHn=∑k=1nLk,LH_n=\sum_{k=1}^{n}\frac{L}{k},

中,L/2rL/2^r 为奇数,其余各项均为偶数,因为在不超过 nn 的整数中,只有 2r2^r 能被 2r2^r 整除。因此,LHnLH_n 为奇数,而 LL 为偶数,所以 HnH_n 不可能是整数。

增长与发散

与 1/x1/x 的积分比较可得

ln⁡(n+1)≤Hn≤1+ln⁡n(n≥1),\ln(n+1)\leq H_n\leq1+\ln n \qquad(n\geq1),

其中 ln⁡\ln 表示自然对数。这些不等式既说明 HnH_n 趋于无穷大,也说明

lim⁡n→∞Hnln⁡n=1.\lim_{n\to\infty}\frac{H_n}{\ln n}=1.

证明发散的一种初等方法,是按相邻的二次幂将各项分组:

H2m=1+∑j=1m∑k=2j−1+12j1k.H_{2^m} = 1+\sum_{j=1}^{m} \sum_{k=2^{j-1}+1}^{2^j}\frac1k.

每个内层求和都包含 2j−12^{j-1} 项,且每项至少为 1/2j1/2^j,因此

H2m≥1+m2.H_{2^m}\geq1+\frac m2.

这个下界会无限增大。这也说明,仅凭各项趋于零,并不能保证无穷级数收敛。

欧拉–马歇罗尼常数

HnH_n 与 ln⁡n\ln n 的差趋于欧拉–马歇罗尼常数:

γ=lim⁡n→∞(Hn−ln⁡n)=0.5772156649….\gamma=\lim_{n\to\infty}(H_n-\ln n) =0.5772156649\ldots.

目前尚不清楚它是有理数还是无理数。

更精确的渐近展开为

Hn=ln⁡n+γ+12n−112n2+1120n4−1252n6+O(n−8).H_n = \ln n+\gamma+\frac{1}{2n} -\frac{1}{12n^2} +\frac{1}{120n^4} -\frac{1}{252n^6} +O(n^{-8}).

这里的余项用大O记号表示。该展开可由欧拉–麦克劳林公式推出。它是渐近展开,而不是收敛的无穷级数:在固定阶数处截断后,所得近似的精度会随着 nn 增大而提高。

下面是一组实用的显式界:

12(n+1)<Hn−ln⁡n−γ<12n,n≥1.\frac{1}{2(n+1)} < H_n-\ln n-\gamma < \frac{1}{2n}, \qquad n\geq1.

恒等式与表示形式

有限和

交换有限二重求和的次序可得

∑k=1nHk=(n+1)Hn−n.\sum_{k=1}^{n}H_k=(n+1)H_n-n.

事实上,1/j1/j 这一项出现在 Hj,Hj+1,…,HnH_j,H_{j+1},\ldots,H_n 中,因此它的总贡献为 (n−j+1)/j(n-j+1)/j。

一个相关的恒等式是

∑k=1nHkk=12(Hn2+Hn(2)),Hn(2)=∑k=1n1k2.\sum_{k=1}^{n}\frac{H_k}{k} = \frac12\left(H_n^2+H_n^{(2)}\right), \qquad H_n^{(2)}=\sum_{k=1}^{n}\frac1{k^2}.

将 HnH_n 的平方展开,再把对角项与非对角项分开,即可得到这一恒等式。

调和数还可以表示为交错的二项式和:

Hn=∑k=1n(−1)k+1(nk)1k,H_n= \sum_{k=1}^{n} (-1)^{k+1}\binom nk\frac1k,

其中 (nk)\binom nk 是二项式系数。

积分表示

由有限等比级数可得

Hn=∫011−xn1−x dx.H_n = \int_0^1\frac{1-x^n}{1-x}\,dx.

当 nn 为整数时,x=1x=1 处看似存在的奇点实际上是可去奇点,因为

1−xn1−x=1+x+⋯+xn−1.\frac{1-x^n}{1-x}=1+x+\cdots+x^{n-1}.

逐项积分便得到 1+1/2+⋯+1/n1+1/2+\cdots+1/n。

生成函数

调和数的普通生成函数为

∑n=0∞Hnxn=−ln⁡(1−x)1−x,∣x∣<1.\sum_{n=0}^{\infty}H_nx^n = -\frac{\ln(1-x)}{1-x}, \qquad |x|<1.

例如,交换两个绝对收敛求和的次序即可推出此式:

∑n=1∞∑k=1nxnk=11−x∑k=1∞xkk.\sum_{n=1}^{\infty}\sum_{k=1}^{n}\frac{x^n}{k} = \frac{1}{1-x}\sum_{k=1}^{\infty}\frac{x^k}{k}.

借助生成函数,许多涉及调和数的恒等式都可以转化为幂级数的代数运算。

广义调和数

ss 阶广义调和数定义为

Hn(s)=∑k=1n1ks.H_n^{(s)}=\sum_{k=1}^{n}\frac1{k^s}.

当 ss 为复数时,约定 k−s=exp⁡(−sln⁡k)k^{-s}=\exp(-s\ln k)。普通调和数对应于 s=1s=1 的情形。

对于实数 s>1s>1,这些和随着 nn 增大而收敛:

lim⁡n→∞Hn(s)=ζ(s),\lim_{n\to\infty}H_n^{(s)}=\zeta(s),

其中 ζ\zeta 为黎曼ζ函数。特别地,

lim⁡n→∞Hn(2)=π26.\lim_{n\to\infty}H_n^{(2)}=\frac{\pi^2}{6}.

更一般地,当复数 ss 满足 Re⁡(s)>1\operatorname{Re}(s)>1 时,这些和也收敛。对于实数 s≤1s\leq1,这些和则发散至正无穷大。

当 s=0s=0 时,Hn(0)=nH_n^{(0)}=n。负整数阶对应于正整数幂之和,例如

Hn(−1)=∑k=1nk=n(n+1)2.H_n^{(-1)}=\sum_{k=1}^{n}k=\frac{n(n+1)}2.

向非整数下标的推广

双伽马函数 ψ\psi 是伽马函数的对数导数,满足

Hn=ψ(n+1)+γ.H_n=\psi(n+1)+\gamma.

由此可作出标准推广:

Hz=ψ(z+1)+γ.H_z=\psi(z+1)+\gamma.

这一定义给出了一个复变量亚纯函数,其极点位于负整数处,并且在等式两边均有定义的地方,仍满足递推关系

Hz−Hz−1=1zH_z-H_{z-1}=\frac1z

。仅要求在非负整数处取值一致,并不能唯一确定推广方式;双伽马函数公式指定了通常采用的那一种。

在概率论与算法中的应用

当一个过程由连续多个阶段构成,且各阶段的等待时间或成功概率涉及倒数关系时,往往会出现调和数。

集齐优惠券

在集齐优惠券问题中,每次独立抽取都会等概率地得到 nn 种优惠券中的一种。已经出现 kk 种不同的优惠券后,下一次抽到新种类的概率为 (n−k)/n(n-k)/n。因此,获得下一种新优惠券所需抽取次数的期望为 n/(n−k)n/(n-k)。

将各阶段的期望相加可得

E[T]=∑k=0n−1nn−k=nHn.\mathbb E[T] = \sum_{k=0}^{n-1}\frac{n}{n-k} =nH_n.

因此,集齐所有种类所需等待时间的期望值按 nln⁡nn\ln n 的速度增长。

随机序列中的纪录

设 X1,…,XnX_1,\ldots,X_n 是来自同一连续概率分布的独立观测值。如果第 kk 个观测值大于它之前的所有观测值,就称其创下新高纪录。由对称性,前 kk 个观测值中的每一个都有相同的概率成为其中的最大值,因此 XkX_k 创下纪录的概率为 1/k1/k。再由期望的线性性质可得

E[number of record highs]=Hn.\mathbb E[\text{number of record highs}]=H_n.

快速排序

对 nn 个互不相同的键值执行随机化快速排序,若每次都从当前子数组中均匀随机选取枢轴,并在划分时将其余每个键值与枢轴各比较一次,则比较次数的期望为

E[Cn]=2(n+1)Hn−4n.\mathbb E[C_n]=2(n+1)H_n-4n.

由于 HnH_n 按对数速度增长,上式的主导项为 2nln⁡n2n\ln n。这是对随机枢轴选择取平均得到的结果,并非每次执行都满足的界;极不均衡的划分可能使比较次数达到平方量级。

数值计算

直接计算需要进行 nn 次求倒数运算和加法。当 nn 很大,且只需要近似值而非精确分数时,使用渐近展开通常更高效。

在浮点运算中,将越来越小的项加到不断增大的总和上,可能导致低位信息丢失。从较小项向较大项依次求和,或采用补偿求和,可以减少这种舍入误差的累积。精确的有理数运算可以避免舍入,但可能需要处理很大的整数分子和分母。