7.14 闲话：离散与连续的结合 —— 积分技巧的应用

· · 个人记录

今天看到有这样一个题，我们先来简单算一下。

\sum_{k=1}^\infty \frac{H_k}{k(k+2)}=\frac 12\sum_{k=1}^\infty H_k \left( \frac{1}{k}-\frac{1}{k+2}\right)

这里就是用积分技巧的精髓了，把 1/k 这种项变为 x^k，以便进行操作：

\frac 12 \int_0^1 \sum_{k=1}^\infty H_k(x^{k-1}-x^{k+1})\text dx

而我们知道

\sum_{k=1}^\infty H_kx^k=\frac{\ln(1-x)}{x-1}

故原式为

-\frac 12 \int_0^1 \ln(1-x)\left( 1+\frac 1x\right)\text dx

拆成两项分别积分，可以得到答案是 \dfrac 12\left( 1+\dfrac{\pi^2}{6}\right)。

不仅是对于级数求和，求部分和也通常很有效。如 EI 的这篇 blog 中所提到的一样。原文讲的比较清楚，这里就不复读了。我们先来看个简单的式子：

\sum_{k= 0}^n\begin{Bmatrix} n \\ k\end{Bmatrix}\frac{(-1)^k}{k+1}k!

第一步就是往积分的形式上转化，变为

\int_{-1}^0 \sum_{k=0}^n \begin{Bmatrix} n \\ k\end{Bmatrix} k!x^k \text dx

注意到 k>n 的项都为零，k 可以直接取到正无穷，这有利于接下来的推导。同时把第二类 Stirling 数用其每列的生成函数表示：

n![z^n]\int_{-1}^0 \sum_{k=0}^\infty (\text e^z-1)^kx^k\text dx =n![z^n]\int_{-1}^0 \frac{\text dx}{1-x(\text e^z-1)} =n![z^n] \frac{z}{\text e^z-1}=B_n

其中 B_n 表示 Bernoulli 数。

再来看看一个更复杂的和式（出自《具体数学》）：

\sum_{k=1}^n\binom nk \frac{(-1)^{k-1}}{k}(n-k)^n

看到求和项中有个 (-1)^{k-1}/k，就可以搞成积分的形式，化为

\int_{-1}^0 \sum_{k=1}^n \binom nk x^{k-1}(n-k)^n\text dx =n![y^n]\int_{-1}^0 \sum_{k=1}^n \binom nk x^{k-1}\text e^{(n-k)y} \text dx

做到这里别急着把被积函数化为封闭形式，而应该把二项式系数用递推式不断拆开，再利用二项式定理变成

n![y^n]\int_{-1}^0 \sum_{k=1}^n \text e^{(n-k)y}(x+\text e^y)^{k-1}\text dx

逐项积分得到

n![y^n]\sum_{k=1}^n \text e^{(n-k)y}\frac{\text e^{ky}-(\text e^y-1)^k}{k} =n^nH_n-n![y^n]\sum_{k=1}^n \frac{\text e^{(n-k)y}(\text e^y-1)^k}{k} =n^nH_n-n![y^n]\text e^{ny}\sum_{k=1}^n \frac{(1-\text e^{-y})^k}{k}

这里又可以利用上一题的技巧，把 k 取到无穷大，这有助于我们把答案写为

n^nH_n-n![y^n]\text e^{ny}(-\ln \text e^{-y})=n^n(H_n-1)

完美解决，这个做法与书上提到的几种都不同。

关于积分这个技巧，还可以对生成函数进行一些奇妙的变换。比如 Laplace 变换可以使生成函数的 x^n 系数乘上 n!，可以视作 EGF 到 OGF 的转化：

\int_0^{+\infty}F(xt)\text e^{-t}\text dt=\sum_{i=0}^\infty f_i x^i \int_0^{+\infty} t^i \text e^{-t}\text dt

后面乘的那个积分很明显是 i!。但实际应用的时候还要多加注意，比如：

\int_0^{+\infty} \text e^{tx}\text e^{-t}\text dt = \frac{\text e^{(x-1)t}}{x-1} \bigg|_{t=0}^{+\infty}

对于某些 x 这个积分可能不收敛，但这里是对形式幂级数操作，就默认它是收敛的了。也就是说，在这里进行的所谓 Laplace 变换，实际上并不是定积分，而是其不定积分取 x=0 的结果的相反数。

这里以推导第二类 Stirling 数每列的 OGF 为例：

\frac{1}{k!}\int_0^{+\infty} (\text e^{tx}-1)^k\text e^{-t}\text dt =\frac{x}{(k-1)!}\int_0^{+\infty}(\text e^{tx}-1)^{k-1}\text e^{(x-1)t}\text dt = \frac{x^2}{(1-x)(k-2)!}\int_0^{+\infty}(\text e^{tx}-1)^{k-2}\text e^{(x-2)t}\text dt

如此不断使用分部积分，就得到了

\sum_{n=k}^\infty \begin{Bmatrix}n \\ k \end{Bmatrix} x^n=x^k\prod_{i=1}^k \frac{1}{1-ix}

此外，由于 \text e^{-t} 这种项在使用分部积分时的性质，也可以导出一些递推式。比如

\sum_{i=0}^\infty i! [x^i]F(x)^n=\int_0^{+\infty}F(t)^n\text e^{-t}\text dt

如果 F'(t) 有一些特殊的性质的话，就可以构建一个整式递推式组来得到答案。比如 loj3411 就是一个典型例题，但这篇文章的篇幅已经够长了（其实是我懒得把别人说过的再复读了），就不再详细介绍，到此为止。

总结下来，个人感觉这确实是一种「技巧」。也有可能是我个人水平不够，还没有发现其足够强的通用性。不过在某些时候这东西确实挺好玩的。