调和级数的前 n 项和

在推导大模型 Decoder 的自注意力的算术强度时，遇到了如下的数列求和问题：

\begin{aligned} \sum_{i = 1}^{S_{o u t}} \frac{1}{S_{i n} + i} \\ = & \sum_{i = 1}^{S_{o u t}} \frac{1}{i} - \sum_{i = 1}^{S_{i n}} \frac{1}{i} \end{aligned}

这涉及到求调和级数的前 $n$ 项和。所以，本文来研究这个问题。

调和级数的敛散性

我们知道， $p$ -级数具有如下敛散性

\begin{array}{r} \sum_{n = 1}^{\infty} \frac{1}{n^{p}} {\begin{cases} 发散, & p ⩽ 1 \\ 收敛, & p > 1 \end{cases} \end{array}

当 $p = 1$ 时，原级数即为调和级数

\begin{array}{r} \sum_{n = 1}^{\infty} \frac{1}{n} \end{array}

为了求出调和级数的前 $n$ 项和，我们需要构造和函数

\begin{aligned} f_{n} (x) & = \sum_{k = 1}^{n} \frac{x^{k}}{k} \end{aligned}

将调和级数表示成幂级数 $f_{n} (x)$ 在 $x = 1$ 处的函数值 $f_{n} (1)$ 。首先对 $f_{n} (x)$ 求一阶导数

\begin{aligned} f_{n}^{'} (x) & = \sum_{k = 1}^{n} x^{k - 1} \\ = \frac{1 - x^{n}}{1 - x} \end{aligned}

两边积分，得到

\begin{aligned} f_{n} (x) & = \int \frac{1 - x^{n}}{1 - x} d x \\ ⟹ f_{n} (1) & = \int_{0}^{1} \frac{1 - x^{n}}{1 - x} d x + f_{n} (0) \\ = \int_{0}^{1} \frac{1 - x^{n}}{1 - x} d x \end{aligned}

求解上述定积分需要借助 Gamma 函数和 Digamma 函数。

我们知道，Gamma 函数的定义最初是为了快速计算阶乘的值。它满足

Γ (x) = x Γ (x - 1)

欧拉给出了 Gamma 函数的积分定义形式

\begin{aligned} Γ (x) & = \int_{0}^{+ \infty} t^{x - 1} e^{- t} d t \end{aligned}

Gamma 函数也被称为第二类欧拉积分。而 Digamma 函数的定义为伽玛函数的对数的导数，即

\begin{aligned} Ψ (x) & = \frac{d \ln Γ (x)}{d x} \\ = \frac{Γ^{'} (x)}{Γ (x)} \end{aligned}

对 Gamma 函数求导，有

\begin{aligned} Γ^{'} (x) & = \frac{d}{d x} \int_{0}^{+ \infty} t^{x - 1} e^{- t} d t \\ = \int_{0}^{+ \infty} t^{x - 1} e^{- t} \ln t d t \\ ⟹ Γ^{'} (1) & = \int_{0}^{+ \infty} e^{- t} \ln t d t \\ = \int_{0}^{1} e^{- t} \ln t d t + \int_{1}^{+ \infty} e^{- t} \ln t d t \\ = \int_{0}^{1} \frac{e^{- t} - 1}{t} d t + \int_{1}^{+ \infty} \frac{e^{- t}}{t} d t \\ = - lim_{n \to \infty} (\sum_{k = 1}^{n} \frac{1}{k} - \ln n) \end{aligned}

这里省略了中间非常复杂的计算。不过，最终我们得到了一个极限，其中恰好包含调和级数和对数函数。如果能够证明这个极限收敛，就能求出调和级数的前 $n$ 项和。

首先给出结论：虽然调和级数以及极限

\begin{array}{r} lim_{n \to \infty} \ln n \end{array}

都发散，但是它们的差

\begin{aligned} γ & = lim_{n \to \infty} γ_{n} \\ = lim_{n \to \infty} (\sum_{k = 1}^{n} \frac{1}{k} - \ln n) \end{aligned}

收敛。通过 $γ_{n}$ 单调递减且有下界，可以证明这个极限存在。我们可以通过计算机求解出这个近似值为

\begin{array}{r} γ \approx 0.5772156649 \end{array}

它被称作欧拉常数。目前，尚不能证明欧拉常数是有理数还是无理数。

这同时也说明了，调和级数和对数函数是同阶无穷大，即当 $n \to \infty$ 时

\begin{array}{r} \sum_{k = 1}^{n} \frac{1}{k} \sim \ln n \end{array}

至此，其实我们可以估算调和级数的前 $n$ 项和为

\begin{array}{r} \sum_{k = 1}^{n} \frac{1}{k} \approx \ln n + γ \end{array}

并且可以证明

\begin{array}{r} \ln (n + 1) < \sum_{k = 1}^{n} \frac{1}{k} < \ln n + 1 \end{array}

有了欧拉常数 $γ$ ，通过一系列推导，可以得到 Digamma 函数的积分形式

\begin{aligned} Ψ (x) & = - γ + \int_{0}^{1} \frac{1 - t^{x - 1}}{1 - t} d t \end{aligned}

做好了上述铺垫后，我们就可以用 Digamma 函数来计算调和级数的前 $n$ 项和

\begin{aligned} \sum_{k = 1}^{n} \frac{1}{n} & = f_{n} (1) \\ = \int_{0}^{1} \frac{1 - t^{n}}{1 - x} d x \\ = Ψ (n + 1) + γ \end{aligned}