《具体数学》 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} \]