有限微积分与求和式

有限微积分是一种处理普通和式的利器，其类比了我们平时见到的无限微积分的知识。

from 《具体数学》2.6。

定义

我们知道，无限微积分中定义的微分算子 $\mathrm{D}$（求导）满足

$$\mathrm{D}f(x) = \frac{\mathrm{d}}{\mathrm{d}x}f(x)=\lim_{h\to 0}\frac{f(x + h) - f(x)}{h}$$

有限微积分则是基于差分算子 $\Delta$。

$$\Delta f(x) = f(x + 1) - f(x)$$

注意此处的差分定义可能与 OI 中常见的差分数组定义不同。

差分算子满足的一条美妙性质可以与微分算子媲美：

$$\Delta(x^{\underline{m}}) = mx^{\underline{m - 1}}$$

与 $\mathrm{D}(x^m) = mx^{m - 1}$ 十分相似。

无限微积分中，有个东西叫做积分，是微分的逆运算：

$$g(x) = \mathrm{D}f(x) \Longleftrightarrow \int g(x)\mathrm{d}x = f(x) + C$$

类似地，差分的逆运算显然是求和：

$$g(x) = \Delta f(x) \Longleftrightarrow \sum g(x)\delta x = f(x) + C$$

我们称之为不定和式（类比不定积分）。

无限微积分存在定积分，若 $g(x) = \mathrm{D}f(x)$，那么：

$$\int^{b}_{a}g(x)\mathrm{d}x = f(x)\big |_{a}^{b} = f(b) - f(a)$$

那么有限微积分应该也有定和式，若 $g(x) = \Delta f(x)$，那么：

$$\sum\nolimits_{a}^{b}g(x)\delta x = f(x)\big |_{a}^{b} = f(b) - f(a)$$

这玩意太玄学了！不过，经过大眼观察，可以发现

$$\sum\nolimits_{a}^{b}g(x)\delta x = \sum_{i = a}^{b - 1}g(i)$$

基本性质

定和式显然满足定积分中的一些性质，如

$$\sum\nolimits_{a}^{b}g(x)\delta x + \sum\nolimits_{b}^{c}g(x)\delta x = \sum\nolimits_{a}^{c}g(x)\delta x$$

$$\sum\nolimits_{a}^{b}(f(x) + g(x))\delta x = \sum\nolimits_{a}^{b}f(x)\delta x + \sum\nolimits_{a}^{b}g(x)\delta x$$

这时候可能就会想到了，上面说了下降幂在有限微积分中可以类比连续情况下的普通幂，那么在求解关于下降幂的和式时，有没有一种简单方法？没错：

$$\sum_{0\le k < n}k^{\underline{m}} = \sum\nolimits_{0}^{n}k^{\underline{m}} = \left.\frac{k^{\underline{m + 1}}}{m + 1}\right |_{0}^{n} = \frac{n^{\underline{m + 1}}}{m + 1}$$

这启发我们：在求解和式的时候，考虑有限微积分的可能性。

例如求解

$$\sum_{k = 1}^{n}k^2$$

时，考虑到 $k^2 = k(k - 1) + k = k^{\underline{2}} + k$，可以得出

$$\begin{aligned} \sum_{k = 1}^{n}k^2 & = \sum\nolimits_{1}^{n + 1}(x^{\underline{2}} + x)\delta x\\ & = \left.\left(\frac{x^{\underline{3}}}{3} + \frac{x^{\underline{2}}}{2}\right)\right|_{1}^{n + 1} \\ & = \frac{2n(n - 1)(n + 1) - 3n(n + 1)}{6} \\ & = \frac{n(n + 1)(2n + 1)}{6} \end{aligned}$$

非常的无脑。只需要用人脑做普通多项式转下降幂多项式。

更多差分

首先，可以将下降幂推广到指数 $< 0$ 的情况。

观察到：

$$\begin{aligned} x^{\underline{3}} & = x(x - 1)(x - 2) \\ x^{\underline{2}} & = x(x - 1) \\ x^1 & = x \\ x^{\underline{0}} & = 1 \end{aligned}$$

那我们显然可以继续向下写：

$$\begin{aligned} x^{\underline{-1}} & = \frac{1}{x + 1} \\ x^{\underline{-2}} & = \frac{1}{(x + 1)(x + 2)} \\ x^{\underline{-3}} & = \frac{1}{(x + 1)(x + 2)(x + 3)} \end{aligned}$$

因此我们可以给出负指数下降幂的定义：

$$x^{\underline{-m}} = \frac{1}{(x + 1)(x + 2)\cdots (x + m)}\quad(m > 0)$$

这种定义能使下降幂推广前的美好性质得到满足。

由此可见：

$$\sum\nolimits_{a}^{b} x^{\underline{m}}\delta x = \left.\frac{x^{\underline{m + 1}}}{m + 1}\right|_{a}^{b}, \quad m \neq -1.$$

那么问题来了，$x^{\underline{-1}}$ 的不定和式是什么呢？

换句话说，我们需要求一个满足 $\Delta f(x) = x^{\underline{-1}} = \frac{1}{x + 1}$ 的 $f(x)$。

那 $f(x)$ 不就是 $H_x$（调和级数）吗？

$$\sum x^{\underline{-1}}\delta x = H_x + C$$

类似地，考虑在无限微积分中，$\int x^{-1}$ 的值。

$$\int x^{-1}\mathrm{d}x = \ln x + C$$

因此，可以得出：调和级数 $H_x$ 是对 $\ln x$ 的有限模拟。

现在下降幂的不定和式就可以直接得出了：

$$\sum x^{\underline{m}}\delta x = \begin{dcases} \frac{x^{\underline{m + 1}}}{m + 1} + C, & m \neq -1\\ H_x + C, & m = -1 \end{dcases}$$

既然有了 $\ln x$ 在有限情况下的对应物，不难想到去找 $\mathrm{e}^x$ 的类似物。

回忆一下：$\mathrm{D}\mathrm{e}^x = e^x$。我们可以找一找满足 $\Delta f(x) = f(x)$ 的函数 $f(x)$ 作为 $\mathrm{e}^x$ 的有限模拟。

$$\begin{aligned} f(x) & = \Delta f(x) \\ & = f(x + 1) - f(x)\\ \therefore f(x + 1) &= 2f(x) \\ \end{aligned}$$

因此，我们可以取 $f(x) = 2^x$ 作为离散指数函数。

类似地，$\Delta c^x$ 也非常好求。

$$\begin{aligned} \Delta c^x & = c^{x + 1} - c^x \\ & = (c - 1)c^x \end{aligned}$$

分部求和

首先，我们知道无限微积分中有个东西叫做链式法则：

$$\frac{\mathrm{d}y}{\mathrm{d}u}\cdot \frac{\mathrm{d}u}{\mathrm{d}x} = \frac{\mathrm{d}y}{\mathrm{d}x}$$

换句话说：

$$(f(g(x)))' = f'(g(x))\cdot g'(x)$$

但是，在有限微积分中并没有对应的链式法则，因为在这一体系中定义域仅为整数集的函数值域却是实数集，导致复合函数多数情况下没有定义。

不过，在无限微积分中的乘积法则

$$\mathrm{D}(uv) = u\mathrm{D}v + v\mathrm{D}u$$

即

$$\frac{\mathrm{d}}{\mathrm{d}x}(uv) = u\frac{\mathrm{d}v}{\mathrm{d}x} + v\frac{\mathrm{d}u}{\mathrm{d}x}$$

可以导出分部积分法则：

$$\int u\mathrm{D}v\ \mathrm{d}x = uv - \int v\mathrm{D}u\ \mathrm{d}x$$

在有限情况下有一个对应，即乘积差分法则：

$$\begin{aligned} \Delta(u(x)v(x)) & = u(x + 1)v(x + 1) - u(x)v(x) \\ & = u(x + 1)v(x + 1) - u(x)v(x + 1) + u(x)v(x + 1) - u(x)v(x) \\ & = (u(x + 1) - u(x))v(x + 1) + u(x)(v(x + 1) - v(x)) \\ & = u(x)\Delta v(x) + v(x + 1)\Delta u(x) \end{aligned}$$

emm，这种形式有点丑陋，我们引入一个移位算子 $\mathrm{E}$ 满足

$$\mathrm{E}f(x) = f(x + 1)$$

那么就可以写出

$$\Delta(uv) = u\Delta v + \mathrm{E}v\Delta u$$

对着它两边求和，我们可以得到分部求和法则：

$$\sum u\Delta v\ \delta x = uv - \sum \mathrm{E}v\Delta u\ \delta x$$

我们可以使用分部积分求解 $\int x\mathrm{e}^x\mathrm{d}x$，取 $u = x$，$\mathrm{D}v = \mathrm{e}^x$，那么 $\mathrm{D}u = 1$，$v = \mathrm{e}^x$：

$$\begin{aligned} \int x\mathrm{e}^x \mathrm{d}x & = \int u\mathrm{D}v\ \mathrm{d}x \\ & = uv - \int v\mathrm{D}u\ \mathrm{d}x \\ & = x\mathrm{e}^x - \int \mathrm{e}^x\mathrm{d}x \\ & = x\mathrm{e}^x - \mathrm{e}^x + C \end{aligned}$$

类似地，我们可以用分部求和法则求解 $\int x\mathrm{e}^x\mathrm{d}x$ 的有限模拟 $\sum x2^x\mathrm{d}x$。

取 $u = x$，$\Delta v = 2^x$，那么 $\Delta u = 1$，$v = 2^x$，$\mathrm{E}v = 2^{x + 1}$。

$$\begin{aligned} \sum x2^x\delta x & = \sum u\Delta v\ \delta x\\ & = uv - \sum \mathrm{E}v\Delta u\ \delta x \\ & = x2^x - \sum2^{x + 1}\delta x \\ & = x2^x - 2^{x + 1} + C \end{aligned}$$

这样，我们可以方便地求出和式 $\sum_{k = 0}^{n}k2^k$ 的值：

$$\begin{aligned} \sum_{k = 0}^{n}k2^k & = \sum\nolimits_{0}^{n + 1}x2^x\delta x \\ & = \left.x2^x - 2^{x + 1}\right|_{0}^{n + 1} \\ & = \left((n + 1)2^{n + 1} - 2^{n + 2}\right) - (0\times 2^0 - 2^{0 + 1}) \\ & = (n - 1)2^{n + 1} + 2 \end{aligned}$$

类似地，我们可以求出 $\sum_{k=0}^{n}H_k$ 的值。

取 $u = H_x$，$\Delta v = 1$，那么 $\Delta u = x^{\underline{-1}}$，$v = x$，$\mathrm{E} v = x + 1$。

则

$$\begin{aligned} \sum H_x\delta x & = \sum u\Delta v\ \delta x\\ & = uv - \sum \mathrm{E}v\Delta u\ \delta x \\ & = xH_x - \sum (x + 1) \cdot x^{\underline{-1}}\delta x\\ & = xH_x - \sum (x + 1) \cdot \frac{1}{x + 1}\delta x \\ & = xH_x - \sum 1\ \delta x\\ & = xH_x - x + C \end{aligned}$$

那么

$$\begin{aligned} \sum_{k = 0}^{n}H_k &= \sum\nolimits_{0}^{n + 1}H_x\delta x \\ & = \left.xH_x - x\right|_{0}^{n + 1} \\ & = (n + 1)H_{n + 1} - (n + 1) \end{aligned}$$