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