一篇简短的离散微积分

一直在看Coursera上宾夕法尼亚大学的微积分课。前两天才看到Discrete Calculus那一节，发现非常有趣，对于探讨函数和数列的一些内在联系非常有启发性，此文略记一二。

囿于作者的数学能力，此文只需高中数学水平就能看懂。首先，我们都知道数列可以看成是定义在自然数集上的特殊函数。重新审视微分或求导的定义， $\frac{d}{d x} f (x) = lim_{h \to 0} \frac{f (x + h) - f (x)}{h}$ 不难发现，如果要把相似的概念应用到数列之中，由于连续变成步长为1的离散，我们不需要取极限，只需要令 $h = 1$ ，就有了差分运算： $Δ a_{n} = a_{n + 1} - a_{n}$ 正如微分可以用来探讨函数的单调性，差分可以用来探讨数列的单调性。在高中数学中其实经常这么干。显然在某一区间上，若 $Δ a_{n} \geq 0$ 数列递增， $Δ a_{n} \leq 0$ 数列递减，当然要对端点处值略加注意。同时，正如微分也可以用来找函数的极大值和极小值，差分亦可用来找数列的极大值和极小值点，那自然是 $Δ a_{n}$ 和 $Δ a_{n - 1}$ 符号发生改变处（含0）。这都是显而易见的，所以不作严格的论证。正如积分是微分的逆运算，求和是差分的逆运算。不难发现， $\sum_{n = A}^{B} Δ a_{n} = \sum_{n = A}^{B} a_{n + 1} - a_{n} = a_{B + 1} - a_{A} = a_{n} |_{A}^{B + 1}$ 需要注意的只是一点求值界限的移动，从微积分里面的 $B$ 变成了 $B + 1$ 。这结论能简单地揭示“裂项求和”的本质，那就是，对于一个待求和的数列 $b_{n}$ ，我们将它写成 $Δ a_{n}$ 的形式（裂项的形式），就一定能容易地得到求和的结果。给个例子。如果 $b_{n} = \frac{1}{n^{2} + 3 n + 2}$ 要对之求和，则是先对 $b_{n}$ 进行代数变形， $b_{n} = \frac{1}{n^{2} + 3 n + 2} = \frac{(n + 2) - (n + 1)}{(n + 2) (n + 1)} = \frac{1}{n + 1} - \frac{1}{n + 2}$ 不难发现应当取 $a_{n} = - \frac{1}{n + 1}$ 就有 $\sum_{n = 1}^{k} b_{n} = \sum_{n = 1}^{k} Δ a_{n} = a_{n} |_{1}^{k + 1} = - \frac{1}{k + 2} + \frac{1}{2}$ 就是答案。在微积分的世界中，我们有一些美好的微分公式。比如，对于多项式，我们有 $\frac{d}{d x} x^{n} = n x^{n - 1}$ 在离散数学的世界中，不存在这一简洁的关系。但是，如果定义 $n^{\underset{―}{m}} = n (n - 1) (n - 2) \dots (n - m + 1)$ 称为 falling factorial. 注意这还是一个关于 $n$ 的 $m$ 次多项式。那么存在 $Δ n^{\underset{―}{m}} = m n^{\underset{―}{m - 1}}$ 依然非常优雅。以此可以简单地推出相应的求和公式，即 $\sum_{n = 1}^{k} n^{\underset{―}{m}} = \frac{n^{\underset{―}{m + 1}}}{m + 1} |_{1}^{k + 1}$ 一个例子是 $\sum_{n = 1}^{k} n^{2} = \sum_{n = 1}^{k} n^{\underset{―}{2}} + n^{\underset{―}{1}} = \frac{n^{\underset{―}{3}}}{3} + \frac{n^{\underset{―}{2}}}{2} |_{1}^{k + 1} = \frac{(k + 1) k (k - 1)}{3} + \frac{(k + 1) k}{2} = \frac{(k + 1) k (2 k + 1)}{6}$ 这样，所有难度其实都集中在 falling factorial 和一般的多项式的代数互化上了。对于指数函数，我们有微分公式： $\frac{d}{d x} a^{x} = a^{x} \ln a$ 相应地，对于等比数列，我们有差分公式： $Δ q^{n} = (q - 1) q^{n}$ 原来都是给自己乘个常数！我们关注这常数是1的情形。那么对于数列来说， $q = 2$ 。对于指数函数来说， $a = e$ 。似乎在离散的世界中， $e$ 变成了2. 我们还知道Product Rule $(f g)^{'} = f^{'} g + f g^{'}$ 对应的差分公式有 $Δ (a_{n} b_{n}) = (Δ a_{n}) b_{n + 1} + (Δ b_{n}) a_{n} = (Δ b_{n}) a_{n + 1} + (Δ a_{n}) b_{n}$ 这证明是非常容易的。但是，记得分部积分吗？正是从微分乘法公式推导而来的： $\int u d v = u v - \int v d u$ 相应地，我们有 $\sum_{n = A}^{B} a_{n} (Δ b_{n}) = a_{n} b_{n} |_{A}^{B + 1} - \sum_{n = A}^{B} (Δ a_{n}) b_{n + 1}$ 正如我们会用分部积分求 $\int x e^{x}$ ，我们用上面这公式去求 $\sum_{n = 1}^{k} n 2^{n}$ 令 $a_{n} = n$ ， $Δ b_{n} = 2^{n}$ ，那么 $Δ a_{n} = 1$ , $b_{n} = 2^{n}$ ,得到 $\sum_{n = 1}^{k} n 2^{n} = n 2^{n} |_{1}^{k + 1} - \sum_{n = 1}^{k} 2^{n + 1} = (k + 1) 2^{k + 1} - 2 - (2^{k + 2} - 4) = (k - 1) 2^{k + 1} + 2$ 最后放两个参考链接：