[具体数学]第六章·特殊的数（第二部分）
第六章·特殊的数分7节，包括斯特林数、欧拉数、调和数、调和求和法、伯努利数、斐波那契数和连项式的内容。这是笔记第二部分，包括调和数、调和求和法、伯努利数。
调和数
\[ \color{purple}{H_n=1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}=\sum_{k=1}^n\frac{1}{k}} \]
从两个例子引入
例一
将 \(n\) 张长度为 \(2\) 纸牌摞在桌边，尽可能地向外伸出，求伸出长度。
我们放置牌的方法应是：上面 \(k\) 张牌的重心恰好在第 \(k+1\) 张牌的边缘处。设从上往下数第 \(k\) 张牌的边缘到第 \(1\) 张牌的边缘距离为 \(d_k\)（\(d_1=0\)），则： \[ d_{k+1}=\frac{(d_1+1)+(d_2+1)+\cdots+(d_k+1)}{k} \] 这是一个 \(k\) 阶递推式，用经典的错位相减可以将其变成 \(1\) 阶递推式： \[ \begin{align} &kd_{k+1}-(k-1)d_k=\sum_{i=1}^k(d_k+1)-\sum_{i=1}^{k-1}(d_k+1)=d_k+1\\ \implies &d_{k+1}=d_k+\frac{1}{k}\\ \implies&d_{k+1}=\frac{1}{k}+\frac{1}{k-1}+\cdots+1=H_k \end{align} \]
例二
一只蠕虫从一根 \(1\text{m}\) 长的橡皮筋的一段开始爬行，每分钟爬行 \(1\text{cm}\)，同时橡皮筋被拉长 \(1\text{m}\)（拉长时，蠕虫在橡皮筋上到起点和终点的比例不变）。蠕虫是否能到达终点？
我们这样考虑：第 \(1\) 分钟后，蠕虫在橡皮筋的 \(\frac{1}{100}\) 处，第 \(2\) 分钟后，蠕虫在橡皮筋的 \(\frac{1}{100}+\frac{1}{200}\) 处……第 \(n\) 分钟后，蠕虫在橡皮筋的 \(\frac{1}{100}H_n\) 处。由于 \(H_n\) 是发散的，蠕虫终会达到终点。
调和数与斯特林数的联系
\[ \newcommand{\stra}[2]{\begin{bmatrix}#1\\#2\end{bmatrix}} \newcommand{\strb}[2]{\begin{Bmatrix}#1\\#2\end{Bmatrix}} \]
回忆第一类斯特林数：\(\stra{n}{k}\) 表示 \(n\) 个物品的 \(k\) 轮换数，满足递归式：\(\stra{n}{k}=(n-1)\stra{n-1}{k}+\stra{n-1}{k-1}\)，所以： \[ \stra{n+1}{2}=n\stra{n}{2}+\stra{n}{1}=n\stra{n}{2}+(n-1)! \] 两边同时除以 \(n!\)，得到： \[ \frac{1}{n!}\stra{n+1}{2}=\frac{1}{(n-1)!}\stra{n}{2}+\frac{1}{n} \] 于是得到： \[ \color{purple}{\stra{n+1}{2}=n!H_n} \]
调和数的估计，黎曼 \(\zeta\) 函数，欧拉常数
调和数是发散的，一个广为人知的证明方式是按照 \(2\) 的幂次分组，这里不再赘述。
我们可以用积分去近似调和数： \[ \int_1^{n+1}\frac{\mathrm dx}{x}<H_n<1+\int_1^n\frac{\mathrm dx}{x} \] 即： \[ \ln(n+1)<H_n<\ln n+1 \]
对调和数进行推广，我们可以得到 \(r\) 次调和数： \[ \color{purple}{H^{(r)}_n=\sum_{k=1}^n\frac{1}{k^r}} \] 如果令 \(n\to\infty\)，那么我们得到黎曼 \(\zeta\) 函数： \[ \color{purple}{\zeta(r)=H^{(r)}_\infty=\sum_{k=1}^\infty\frac{1}{k^r}} \]
欧拉曾发现一个简洁的方法，利用广义调和数 \(H^{(r)}_n\) 来近似调和数 \(H_n\). 首先考虑无穷级数： \[ \ln\left(\frac{k}{k-1}\right)=\frac{1}{k}+\frac{1}{2k^2}+\frac{1}{3k^3}+\cdots \]
附注：令 \(S(k)=\sum\limits_{i=1}^\infty\frac{1}{ik^i}\)，则： \[ S'(k)=\sum_{i=1}^\infty\frac{-1}{k^{i+1}}=-\frac{1}{k^2}\frac{1}{1-\frac{1}{k}}=-\frac{1}{k(k-1)}=\frac{1}{k}-\frac{1}{k-1} \] 于是， \[ S(k)=\int S'(k)\mathrm dk=\ln\left(\frac{k}{k-1}\right) \] 故上述无穷级数成立。
求和有： \[ \begin{align} \sum_{k=2}^n\ln\left(\frac{k}{k-1}\right)=\ln k=\sum_{i=1}^\infty\frac{H^{(i)}_n-1}{i} \end{align} \] 于是我们就对 \(H_n\) 和 \(\ln n\) 的差有一个表达式： \[ H_n-\ln n=1-\frac{1}{2}(H^{(2)}_n-1)-\frac{1}{3}(H^{(3)}_n-1)-\frac{1}{4}(H^{(4)}_n-1)-\cdots \] 当 \(n\to\infty\) 时，有： \[ \lim_{n\to\infty}(H_n-\ln n)=1-\frac{1}{2}(\zeta(2)-1)-\frac{1}{3}(\zeta(3)-1)-\frac{1}{4}(\zeta(4)-1)-\cdots \] 称之为欧拉常数 \(\gamma\)，即： \[ \color{purple}{\gamma=\lim_{n\to\infty}(H_n-\ln n)=1-\frac{1}{2}(\zeta(2)-1)-\frac{1}{3}(\zeta(3)-1)-\frac{1}{4}(\zeta(4)-1)-\cdots} \]
调和求和法
例一
求： \[ \sum_{0\leqslant k<n}\binom{k}{m}H_k \] 回忆分部求和法： \[ \sum\nolimits_a^bu(x)\Delta v(x)\delta x=u(x)v(x)\Big|_a^b-\sum\nolimits_a^bEv(x)\Delta u(x)\delta x \] 由于 \[ \Delta H_k=H_{k+1}-H_k=\frac{1}{k+1}\quad,\quad\Delta \binom{k}{m+1}=\binom{k+1}{m+1}-\binom{k}{m+1}=\binom{k}{m} \] 应用分部求和法有： \[ \begin{align} \sum_{0\leqslant k<n}\binom{k}{m}H_k&=\sum\nolimits_0^nH_k\Delta\binom{k}{m+1}\delta k\\ &=\binom{k}{m+1}H_k\Big|_0^n-\sum\nolimits_0^n\binom{k+1}{m+1}\frac{1}{k+1}\delta k\\ &=\binom{n}{m+1}H_n-\frac{1}{m+1}\sum\nolimits_0^n\binom{k}{m}\delta k\\ &=\binom{n}{m+1}H_n-\frac{1}{m+1}\binom{n}{m+1}\\ &=\binom{n}{m+1}\left(H_n-\frac{1}{m+1}\right) \end{align} \]
例二
求： \[ S_n=\sum_{k=1}^n\frac{H_k}{k} \] 方法1： \[ \begin{align} S_n&=\sum_{k=1}^n\frac{H_k}{k}\\ &=\sum_{k=1}^n\sum_{j=1}^k\frac{1}{jk}\\ &=\frac{1}{2}\left(\sum_{k=1}^n\sum_{j=1}^n\frac{1}{jk}+\sum_{k=1}^n\frac{1}{k^2}\right)\\ &=\frac{1}{2}\left(H_n^2+H_n^{(2)}\right) \end{align} \] 方法2： \[ \begin{align} S_n-H^{(2)}_n&=\sum_{k=1}^n\left(\frac{H_k}{k}-\frac{1}{k^2}\right)\\ &=\sum_{k=1}^n\frac{kH_k-1}{k^2}\\ &=\sum_{k=1}^n\frac{H_{k-1}}{k}\\ &=\sum\nolimits_1^{n+1}H_{k-1}\Delta H_{k-1}\delta k\\ &=H^2_{k-1}\big|_1^{n+1}-\sum\nolimits_1^{n+1}H_k\frac{1}{k}\delta k\\ &=H^2_n-S_n \end{align} \] 于是 \[ S_n=\frac{1}{2}\left(H^2_n+H_n^{(2)}\right) \]
例三
求： \[ U_n=\sum_{k\geqslant 1}\binom{n}{k}\frac{(-1)^{k-1}}{k}(n-k)^n,\quad整数\;n\geqslant 1. \]
将 \((n-k)^n\) 二项展开得： \[ U_n=\sum_{k\geqslant 1}\binom{n}{k}\frac{(-1)^{k-1}}{k}\sum_j\binom{n}{j}(-k)^jn^{n-j}=\sum_{j}\binom{n}{j}(-1)^{j-1}n^{n-j}\sum_{k\geqslant1}\binom{n}{k}(-1)^kk^{j-1} \] 回忆高阶差分公式： \[ \Delta^nf(x)=\sum_{k}\binom{n}{k}(-1)^{n-k}f(x+k) \] 所以有： \[ \begin{align} U_n=&\binom{n}{0}(-1)n^n\sum_{k\geqslant1}\binom{n}{k}(-1)^kk^{-1}&&单独处理\;j=0\\ &+\sum_{j\geqslant 1}\binom{n}{j}(-1)^{j-1}n^{n-j}\sum_{k}\binom{n}{k}(-1)^kk^{j-1}&&补上\;k=0\\ &-\sum_{j\geqslant 1}\binom{n}{j}(-1)^{j-1}n^{n-j}\binom{n}{0}0^{j-1}&&再减去\;k=0\\ =&-n^n\sum_{k\geqslant1}\binom{n}{k}\frac{(-1)^k}{k}\\ &+(-1)^n\sum_{j\geqslant 1}\binom{n}{j}(-1)^{j-1}n^{n-j}\sum_k\binom{n}{k}(-1)^{n-k}k^{j-1}&&凑出高阶差分\\ &-n^n&&只有\;j=1\;时不为零\\ =&n^n\sum_{k\geqslant1}\binom{n}{k}\frac{(-1)^{k-1}}{k}\\ &+0&&次数小于\;n\;的\;n\;阶差分为零\\ &-n^n\\ =&n^n(T_n-1) \end{align} \]
现在，我们只需要求解： \[ T_n=\sum_{k\geqslant 1}\binom{n}{k}\frac{(-1)^{k-1}}{k} \]
将 \(\binom{n}{k}\) 拆开为 \(\binom{n-1}{k-1}+\binom{n-1}{k}\)，则可以用 \(T_{n-1}\) 表示 \(T_n\)： \[ \begin{align} T_n&=\sum_{k\geqslant 1}\left(\binom{n-1}{k-1}+\binom{n-1}{k}\right)\frac{(-1)^{k-1}}{k}\\ &=\sum_{k\geqslant 1}\binom{n}{k}\frac{(-1)^{k-1}}{n}+\sum_{k\geqslant 1}\binom{n-1}{k}\frac{(-1)^{k-1}}{k}\\ &=-\frac{1}{n}\sum_{k\geqslant 1}\binom{n}{k}(-1)^{k}+T_{n-1}\\ &=\frac{1}{n}+T_{n-1} \end{align} \] 又 \(T_1=1\)，故： \[ T_n=H_n \] 所以，我们最终解得： \[ U_n=n^n(H_n-1) \]
伯努利数
定义与自然数幂和
\(\textbf{Jacob Bernoulli}\) 在研究 \(m\) 次幂和时发现了： \[ S_m(n):=\sum_{k=0}^{n-1} k^m=0^m+1^m+\cdots+(n-1)^m=\frac{1}{m+1}\sum_{k=0}^m\binom{m+1}{k}B_kn^{m+1-k} \] 其中伯努利数递归地定义为： \[ \sum_{j=0}^m\binom{m+1}{j}B_j=[m=0],\quad \forall m\geqslant 0 \] 前几个值为：
| \(n\) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| \(B_n\) | \(1\) | \(-\frac{1}{2}\) | \(\frac{1}{6}\) | \(0\) | \(-\frac{1}{30}\) | \(0\) | \(\frac{1}{42}\) | \(0\) | \(-\frac{1}{30}\) | \(0\) | \(\frac{5}{66}\) | \(0\) | \(-\frac{691}{2730}\) |
证明：采用扰动法对 \(m\) 进行归纳： \[ \begin{align} S_{m+1}(n+1)=S_{m+1}(n)+n^{m+1}&=\sum_{k=0}^{n-1}(k+1)^{m+1}\\ &=\sum_{k=0}^{n-1}\sum_{j=0}^{m+1}\binom{m+1}{j}k^j\\ &=\sum_{j=0}^{m+1}\binom{m+1}{j}S_j(n) \end{align} \] 于是： \[ n^{m+1}=\sum_{j=0}^m\binom{m+1}{j}S_j(n) \] 假设伯努利的自然数幂和公式对 \(0\leqslant j<m\) 均成立，记 \(\hat S_m(n)=\frac{1}{m+1}\sum\limits_{k=0}^m\binom{m+1}{k}B_kn^{m+1-k}\)，那么： \[ \begin{align} n^{m+1}&=\sum_{j=0}^m\binom{m+1}{j}\frac{1}{j+1}\sum_{k=0}^j\binom{j+1}{k}B_kn^{j+1-k}+\binom{m+1}{m}\left(S_m(n)-\hat S_m(n)\right)\\ &=\sum_{k=0}^m\sum_{j=k}^m\binom{m+1}{j}\frac{1}{j+1}\binom{j+1}{k}B_kn^{j+1-k}+(m+1)\left(S_m(n)-\hat S_m(n)\right)\\ &=\sum_{k=0}^m\sum_{j=k}^m\binom{m+1}{j}\binom{j+1}{j-k}\frac{B_{j-k}n^{k+1}}{j+1}+(m+1)\left(S_m(n)-\hat S_m(n)\right)\\ &=\sum_{k=0}^m\sum_{j=k}^m\binom{m+1}{j}\binom{j+1}{k+1}\frac{B_{j-k}n^{k+1}}{j+1}+(m+1)\left(S_m(n)-\hat S_m(n)\right)\\ &=\sum_{k=0}^m\frac{n^{k+1}}{k+1}\sum_{j=k}^m\binom{m+1}{j}\binom{j}{k}B_{j-k}n^{k+1}+(m+1)\left(S_m(n)-\hat S_m(n)\right)\\ &=\sum_{k=0}^m\frac{n^{k+1}}{k+1}\sum_{j=k}^m\binom{m+1}{k}\binom{m+1-k}{j-k}B_{j-k}n^{k+1}+(m+1)\left(S_m(n)-\hat S_m(n)\right)\\ &=\sum_{k=0}^m\frac{n^{k+1}}{k+1}\binom{m+1}{k}\sum_{j=k}^m\binom{m+1-k}{j-k}B_{j-k}n^{k+1}+(m+1)\left(S_m(n)-\hat S_m(n)\right)\\ &=\sum_{k=0}^m\frac{n^{k+1}}{k+1}\binom{m+1}{k}\sum_{j=0}^{m-k}\binom{m+1-k}{j}B_{j}n^{k+1}+(m+1)\left(S_m(n)-\hat S_m(n)\right)\\ &=\sum_{k=0}^m\frac{n^{k+1}}{k+1}\binom{m+1}{k}[m=k]+(m+1)\left(S_m(n)-\hat S_m(n)\right)\\ &=\frac{n^{m+1}}{m+1}(m+1)+(m+1)\left(S_m(n)-\hat S_m(n)\right)\\ &=n^{m+1}+(m+1)\left(S_m(n)-\hat S_m(n)\right) \end{align} \] 故： \[ S_m(n)=\hat S_m(n) \] 归纳完毕。