《具体数学》 2.6 有限微积分和无限微积分

注意，本文英文标题是 FINITE AND INFINITE CALCULUS ，不是定积分和不定积分。

本章实际上定义了不定和式 $\sum g(x)\delta x$ 和和式 $\sum_a^bg(x)\delta x$ 。

一、微分算子与差分算子

按照书本中的定义，无限微积分基于由

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

所定义的微分（derivative）算子 $\mathrm{D}$ 的性质。有限微积分则是基于由

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

所定义的差分（difference）算子 $\Delta$ 的性质。

差分算子是微分的有限模拟，其中限制了取 $h$ 的正整数值。

于是当 $h \to 0$ 时，$h=1$ 是我们所能达到的最近的“极限”，则 $\left.\Delta f(x)=\frac{f(x+h)-f(x)}{h}\right|_{h=1}$

符号 $\mathrm{D}$ 和 $\Delta$ 之所以被称为算子（operator），是因为他们作用（operate）在函数上给出新的函数

他们是函数的函数，用于产生函数。实际上 $\mathrm{D}f(x)$ 相当于 $f^{\prime}(x)$ ，即 $f(x)$ 的一阶导数。

我们知道 $f^{\prime}(x^m) = mx^{m-1}$ ，而 $\Delta$ 算子并不能产生这样优美的结果，除了…

二、阶乘幂

定义 $x^{\underline{m}} = x(x-1)\cdots(x-m+1)$ ，整数 $m \ge 0$ 。

类似的，定义 $x^{\overline{m}}=x(x+1)\cdots(x+m-1)$ ，整数 $m\ge 0$ 。

当 $m=0$ 时，我们有 $x^{\underline{0}} = x^{\overline{0}}=1$ 。

如果要大声读出 $x^{\underline{m}}$ ，它称为“ $x$ 直降 $m$ 次”；类似的， $x^{\overline{m}}$ 称为“ $x$ 直升 $m$ 次”。

这些函数分别称为下降阶乘幂（falling factorial power）和上升阶乘幂（rising factorial power）。

有趣的是，符号 $x^{\underline{m}}$ 和 $x^{\overline{m}}$ 正是本书作者引进的符号，或者说是原创的表示方式。

可以证明，$\Delta (x^{\underline{m}}) = mx^{\underline{m-1}}$ （这里作者采用了非正式的写法，即略去了 $f$ ）

三、积分算子与求和算子

无限微积分的算子 $\mathrm{D}$ 有一个逆运算，即逆微分算子（或积分算子）$\int$

$g(x) = \mathrm{D}f(x) \texttt{ 当且仅当 }\int g(x)\mathrm{d}x=f(x) + C$

这里 $\int g(x) \mathrm{d}x$ 是 $g(x)$ 的不定积分，它是导数等于 $g(x)$ 的一个函数类。

类似的，$\Delta$ 也有一个逆运算，即逆差分算子（或求和算子） $\sum$

$g(x) = \Delta f(x) \texttt{ 当且仅当 }\sum g(x) \delta x = f(x) + C$

其中 $\sum g(x) \delta x$ 是 $g(x)$ 的不定和式（indefinite sum），是差分等于 $g(x)$ 的一个函数类

这里小写 $\delta$ 与大写 $\Delta$ 相关，就像 $\mathrm{d}$ 与 $\mathrm{D}$ 有关一样。

在不定积分中 $C$ 是一个任意常数，而不定和式中的 $C$ 则是满足 $p(x+1)=p(x)$ 的任意一个函数。

例如 $C$ 可以是周期函数 $a+b\sin 2\pi x$ ，在求差分时这样的函数会被消去。

有限微积分模仿无线微积分中的定（definite）积分，也有确定的和式：

${\sum}_a^b\,g(x)\delta x = \sum_{k=a}^{b-1}g(k)=\sum_{a \le k < b}g(k) \qquad \texttt{整数}\,b\ge a$

注意这里是 $b-1$ ，因为
$\begin{aligned} {\sum}_a^{b+1} g(x) \delta x-{\sum}_a^b g(x) \delta x & =(f(b+1)-f(a))-(f(b)-f(a)) \\ & =f(b+1)-f(b)=g(b) \end{aligned}$

可以证明：

${\sum}_a^bg(x)\delta x=-{\sum}_b^{a}g(x)\delta x$
${\sum}_{a}^bg(x)\delta x = f(b) - f(a)$ ，其中 $g(x)=\Delta f(x) = f(x+1) - f(x)$
${\sum}_a^bg(x)\delta x + {\sum}_b^cg(x)\delta x={\sum}_a^cg(x)\delta x$

那么这些有什么用呢？~~且听下节分解~~。

四、下降幂和式

实际上我们已经可以证明下面这个重要的公式

$\sum_{0 \le k < n}k^{\underline{m}}=\left.\frac{k^{\underline{m+1}}}{m+1}\right|_0^n = \frac{n^{\underline{m+1}}}{m+1}\qquad \texttt{整数}\,m,n \ge 0$

特别地，当 $m=1$ 时有 $k^{\underline{1}}=k$ ，所以借助有限微积分的原理，有

$\sum_{0 \le k < n}k = \frac{n^{\underline{2}}}{2} = \frac{n(n-1)}{2}$

当然这个公式本来就很好记，因为它很像 $\displaystyle\int_0^n x^m\mathrm{d}x=\frac{n^{m+1}}{m+1}$ 。

确定和式的方法也暗示了，对于范围 $0\le k < n$ 通常比 $1 \le k \le n$ 便于计算

因为前者恰好是 $f(n)-f(0)$ ，而后者则是 $f(n+1)-f(1)$ 。

通常的幂也可以用这样的新方法来求和，如果我们首先用下降幂将它们表示出来，例如

$k^2 = k^{\underline{2}}+k^{\underline{1}}$

所以

$\sum_{0 \le k<n} k^2=\frac{n^{\underline 3}}{3}+\frac{n^{\underline2}}{2}=\frac{1}{3} n(n-1)\left(n-2+\frac{3}{2}\right)=\frac{1}{3} n\left(n-\frac{1}{2}\right)(n-1)$

用 $n+1$ 替换 $n$ 又给出另一种将~~我们的老朋友~~ $\square_n=\sum_{0\le k \le n}k^2$ 计算成封闭形式的方法

确实是老朋友，只不过前面那个章节我现在还没写。

不过坏消息是立方的情况稍微不太一样

$k^3 = k^{\underline{3}} + 3k^{\underline{2}} + k^{\underline{1}}$

（实际上这需要用到本书在第6章研究的斯特林数，将通常的幂与阶乘幂相互转化）从而

$\sum_{a \leqslant k<b} k^3=\frac{k^{\underline 4}}{4}+k^{\underline 3}+\left.\frac{k^{\underline 2}}{2}\right|_a^b$

另外，本书在第5章习题37中给出了对非负整数 $n$ ， $(x+y)^n$ 与 $(x+y)^{\underline n}$ 的有趣关系（的证明）
$(x+y)^{\underline{n}} = \sum_k\binom{n}{k}x^{\underline k}y^{\underline {n - k}} \\[6pt](x+y)^{\overline{n}} = \sum_k\binom{n}{k}x^{\overline k}y^{\overline {n - k}}$

五、负指数的下降幂

观察

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

看上去 $x^{\underline -1}$ 应该除以 $x+1$ 。

于是负指数的下降幂的一般定义是

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

细心的同学一定发现了，这里没有强调 $m$ 为整数，因为在第5章中会对实数甚至复数 $m$ 定义下降幂

下降幂指数法则的形式是

$x^{\underline{m+n}} = x^{\underline{m}}(x-m)^{\underline{n}} \\[6pt]x^{\underline{m-n}} = x^{\underline{m}}(x-m)^{\underline{-n}}$

同时可以证明

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

在 $m < 0$ 时仍成立。以及

${\sum}_a^bx^{\underline{m}}\delta x=\left.\frac{x^{\underline{m+1}}}{m+1}\right|_a^b \qquad (m \ne -1)$

那么 $m=-1$ 时怎么办呢？

回想一下对积分的情形

$\int_a^bx^{-1}\mathrm{d}x=\ln x\Big|_a^b$

也就是说，我们要找到一个函数满足

$x^{\underline{-1}} = \frac{1}{x+1} = \Delta f(x) = f(x + 1) - f(x)$

不难看出，当 $x$ 是整数时，$f(x) = 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{x}$ 。

这不就是调和数 $H_x$ 嘛！于是 $H_x$ 就是连续的 $\ln x$ 的离散模拟（在第6章会对非整数 $x$ 定义 $H_x$ ）。

因此

${\sum}_a^bx^{\underline{m}}\delta x= \begin{cases} \left.\frac{k^{\underline{m+1}}}{m+1}\right|_a^b&m \ne -1 \\[8pt]H_x\big|_a^b &m = -1 \end{cases}$

六、$\mathrm{e}^x$ 的离散模拟

既然我们找到了类似于 $\ln(x)$ 的东西，那有没有 $\mathrm{e}^x$ 对应的呢？

也就是，什么样的函数 $f(x)$ 有与恒等式 $\mathrm{D}\mathrm{e}^x=\mathrm{e}^x$ 对应呢？这很简单

$f(x+1)-f(x)=f(x) \Leftrightarrow f(x+1)=2f(x)$

因此我们是在处理一个简单的递归式，可以取 $f(x)=2^x$ 作为离散指数函数。

$c^x$ 的差分也相当简单，即对任意的 $c$ 有

$\Delta(c^x)=c^{x+1}-c^x=(c-1)c^x$

故而，如果 $c \ne 1$ ，$c^x$ 的逆差分是 $\frac{c^x}{c-1}$

结合逆差分的性质，就给出了理解几何级数和（等比数列的和）的一般公式的满意办法

$\sum_{a \le k < b}c^k = {\sum}_a^bc^x\delta x=\left.\frac{c^x}{c-1}\right|_a^b = \frac{c^b-c^a}{c-1},~c\ne 1$

因此每当遇到一个可能用作封闭形式的函数 $f$ ，我们就能计算出它的差分 $\Delta f=g$

然后就有一个函数 $g$ ，它的不定和式 $\sum g(x)\delta x$ 是已知的。下面贴个书上的表格

$\begin{array}{|lll|lll|} \hline f=\sum g &\quad & \Delta f=g && f=\sum g &\quad& \Delta f=g \\[6pt] \hline x^{\underline 0}=1 && 0 && 2^x && 2^x \\[6pt] \hline x^{\underline 1}=x && 1 && c^x && (c-1) c^x \\[6pt] \hline x^{\underline 2}=x(x-1) && 2 x && \frac{c^x}{c-1} && c^x \\[6pt] \hline x^{\underline m} && m x^{\underline{m-1}} && c u && c \Delta u \\[6pt] \hline \frac{x^{\underline{m+1}}}{m+1} && x^{\underline m} && u+v && \Delta u+\Delta v \\[6pt] \hline H_x && x^{\underline {-1}}=\frac{1}{x+1} && u v && u \Delta v+\mathrm{E} v \Delta u \\[6pt] \hline \end{array}$

这里的 $\mathrm{E}$ 是移位算子，有 $\mathrm{E}f(x)=f(x+1)$ ，下文会提到。

七、移位算子&分部求和法则

尽管在连续数学和离散数学之间有这些对应的结果，但是某些连续概念并没有离散的相似概念。

例如无限微积分的链式法则，在有限微积分中没有对应。

然而 $\Delta(f(x)g(x))$ 的确有比较好的形式，而且提供了一个分部求和（summation by parts）的法则

回顾无限微积分中的公式

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

在积分并重新排列后，它引导出分部积分法

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

于是我们可以类似地推导出

$\Delta(u(x)v(x)) = u(x)\Delta v(x) + v(x+1)\Delta u(x)$

这个公式可以利用由

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

所定义的移位算子（shift operator）$\mathrm{E}$ 表示成方便的形式

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

在这个方程两边取不定和，并重新排列它的项，便得到所谓分部求和法则

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

如同于无限微积分那样，可以在所有三项上加上界限，从而使得不定和式变成确定和式

当左边的式子比右边的式子更难处理时，这个法则是有用的。

我们来看个例子，比如 $\int x\mathrm{e}^x\mathrm{d}x$ 是分部积分的一个典型例子，它的离散模拟是 $\sum x2^x\delta x$ 。

我们在这一章前面以 $\sum_{k=0}^nk2^k$ 的形式遇到过它。

为了用分部求和，我们令 $u(x)=x,~\Delta v(x)=2^x$ ，从而 $\Delta u(x) = 1,~v(x)=2^x$ ，且 $\mathrm{E}v(x)=2^{x+1}$

代入可得

$\sum x 2^x\delta x = x2^x - \sum 2^{x+1}\delta x = x2^x - 2^{x+1}+C$

加上界限，我们可以用此式来计算以前做过的和式

$\begin{aligned} \sum_{k=0}^nk2^k &= {\sum}_0^{n+1}x2^x\delta x \\[6pt] &=x2^x-2^{x+1}\Big|_0^{n+1} \\[6pt] &= \left((n+1)2^{n+1} - 2^{n+2}\right) - (0\times 2^0-2^1) \\[6pt] &= (n-1)2^{n+1}+2 \end{aligned}$

这比扰动法好使多了。

另外，在之前的章节中我们碰巧发现了 $\sum_{0\le k < n}H_k$ 的公式

不过现在我们已经可以证明它了，前提是通过解决一个看似更难的和式 $\sum_{0\le k < n}kH_k$ 。

令 $u(x)=H_x,~\Delta v(x) = x = x^{\underline 1}$ ，从而 $\Delta u(x) = x^{\underline {-1}},~v(x) = \frac{x^{\underline{2}}}{2},~\mathrm{E}v(x) = \frac{(x+1)^{\underline{2}}}{2}$ ，则

$\begin{aligned} \sum x H_x \delta x & =\frac{x^{\underline 2}}{2} H_x-\sum \frac{(x+1)^{\underline 2}}{2} x^{\underline {-1}} \delta x \\ & =\frac{x^{\underline 2}}{2} H_x-\frac{1}{2} \sum x^{\underline 1} \delta x \\ & =\frac{x^{\underline 2}}{2} H_x-\frac{x^{\underline 2}}{4}+C \end{aligned}$