本地稿整理，原稿供班级公众号，写于 2019-09-12，2019-12-08 上传

序

最近数学课上在讲数列。众所周知，我们主要探寻数列的两个属性：

1. 通项公式
2. 前 \(n\) 项和

关于第二点，我们已经在课上学习了等差数列和等比数列前 \(n\) 项和的计算方法，但是更为复杂的数列呢？例如数列 \(\{a_n\},a_n=n^2,n\in\mathbb{N}^{\ast}\) 的前 \(n\) 项和： \[ S_n = \sum_{x=1}^n x^2 \] 或是更复杂一点，\(a_n=2^nn^2,n\in\mathbb{N}^{\ast}\)： \[ S_n = \sum_{x=1}^{n}2^xx^2 \] 或者更复杂呢？

诚然，你可能知道平方和的公式，对于第二个式子也许也有巧办法解决。但是很多方法仍存在不少局限性。有没有更通用的办法呢？

如果你自学过一点基础的微积分，你会不会想到，既然 \[ \int_{1}^n2^xx^2\mathrm{d}x \] 可以通过分部积分比较套路地演算，变成数列之后有没有类似的方法呢？

这篇文章想分享的，就是在通过类比微积分构造出的这样一种系统化的求和方法。

下面的文章如果自学过微积分的话可能会比较好读，没学过也没关系，反正本身不用到任何微积分概念。

这个方法是我在《具体数学》里面看到的，也似乎只有这一本书里讲到这个方法，网上都没有。但是真的很有效，也很成系统，很震撼。这里对记号和名词做了一点小修改并避免了一些概念。

以下统一把数列看做函数，然后因为下面有非常多的函数，一定会牵涉到定义域的问题。但是好在这些函数的定义域都是平凡且显然的，所以就不写了。

基础记号与理念

定义 \(f(x)\) 对于 \(x\) 的差分为且记作： \[ \frac{\mathrm{\delta} f(x)}{\mathrm{\delta} x} = f(x+1)-f(x) \] 易证差分对加减法有分配率： \[ \frac{\mathrm{\delta} \left[f(x) \pm g(x)\right]}{\mathrm{\delta} x} = \frac{\mathrm{\delta} f(x)}{\mathrm{\delta} x} \pm \frac{\mathrm{\delta} g(x)}{\mathrm{\delta} x} \] 且易证其线性： \[ \frac{\mathrm{\delta} kf(x)}{\mathrm{\delta} x} = k\frac{\mathrm{\delta} f(x)}{\mathrm{\delta} x} \] 又易证常数的差分为 \(0\)（显然地）。

若 \(F(x)\) 的差分为 \(f(x)\)，我们观察到对于 \(a,b\in\mathbb{Z}, b > a\)，有： \[ F(b)-F(a) = \sum_{x=a}^{b-1} f(x) \] 那么，一个求和问题就可以被规约为求同一函数两个函数值差的问题。

因此，在这个框架下，如果要计算 \(\sum_{x=a}^b f(x)\)，我们就要：

1. 找到合适的 \(F(x)\)，其差分为 \(f(x)\)
2. 计算 \(F(b+1)-F(a)\)

（前几天课上讲的 “累减法” 是以上步骤的反向简化版）

当中最核心，也是最有意思的一个步骤，自然就是寻找 \(F(x)\)。寻找 \(F(x)\) 的过程本质上是差分的逆运算。不妨把这个逆运算称作” 逆差分 “。因为使用 \(F(x)\) 易产生指代不清的问题，我们为 \(f(x)\) 的逆差分定义如下记号： \[ F(x) = \sum f(x)\mathrm{\delta} x \] 则由定义，可得： \[ \frac{\mathrm{\delta} \left(\sum f(x) \mathrm{\delta} x\right)}{\mathrm{\delta} x} = f(x), \sum \frac{\mathrm{\delta} f(x)}{\mathrm{\delta} x} \mathrm{\delta} x = f(x) \] 举些例子： \[ \begin{aligned} \frac{\mathrm{\delta} x}{\mathrm{\delta} x} = 1 &\Leftrightarrow \sum1\mathrm{\delta} x = x + C\\ \frac{\mathrm{\delta} x^2}{\mathrm{\delta} x} = 2x+1 &\Leftrightarrow \sum (2x+1)\mathrm{\delta} x = x^2 + C \end{aligned} \] 为什么要 \(+C\) 呢？因为 \(f(x)\) 的逆差分不唯一：对于任意已知的 \(f(x)\) 逆差分加上任意的常数依然是 \(f(x)\) 的逆差分（差分的时候常数就抵消掉了）。这里的 \(C\) 便是这个意思。

逆差分由于是差分的逆运算，其对于加法的分配率以及线性亦显然。

接下来的这篇文章的中心便是：如何计算 \(\sum f(x) \mathrm{\delta} x\)？

以下默认 \(x,n \in \mathbb Z\)。

“幂” 法则

对微积分有些许了解的同学一定知道积分当中的幂法则： \[ \int x^m \mathrm{d}x=\frac{x^{m+1}}{m+1}+C \] 它来源于微分的幂法则： \[ \frac{\mathrm{d}x^m}{\mathrm{d}x} = mx^{m-1} \] 类似的幂法则在我们刚刚建立的框架当中的类比是什么呢？

直接把微分换成差分？ \[ \frac{\mathrm{\delta} x^m}{\mathrm{\delta} x} = (x+1)^m-x^m = ? \] 我们发现好像没有什么优雅的结果诶！

会不会是” 幂” 出了问题呢？

定义下降阶乘幂 \(x^{\underline{m}}\)： \[ x^{\underline m} = x(x-1)(x-2)\cdots(x-m+1) = \frac{x!}{(x - m)!} , \quad x>0,m\in \mathbb{Z} \] （当然，最右边那个有阶乘的式子要有意义，应该 \(x\ge m\)，如果 \(x<m\)，那么不妨令整个阶乘幂为 \(0\)）

为什么要定义那么奇怪的幂呢？考查下降阶乘幂的差分： \[ \begin{aligned} \frac{\mathrm{\delta} x^{\underline m}}{\mathrm{\delta} x} &= (x + 1)^{\underline m} - x^{\underline m} \\ &= \frac{(x + 1)!}{(x + 1 - m)!} - \frac{x!}{(x - m)!} \\ &= \frac{(x + 1)! - (x + 1 - m)x!}{(x + 1 - m)!} \\ &= \frac{x![(x + 1) - (x + 1 - m)]}{(x + 1 - m)!} \\ &= \frac{mx!}{[x - (m - 1)]!} \\ &= mx^{\underline{m - 1}} \end{aligned} \] 我们发现在使用下降阶乘幂的情况下，我们就可以把微分当中的幂法则类比到差分当中了。

同时，我们不妨探索一下常规幂的性质在下降阶乘幂中的类比： \[ x^{\underline{m + n}} = x^{\underline m}(x - m)^{\underline n}, \quad m,n\in \mathbb{Z} \] 以及当 \(m<0\) 时： \[ x^{\underline{-m}} = \frac{1}{(x + 1)(x + 2)\cdots(x + m)} \] 这些类比得来的性质有助于我们加深对于下降阶乘幂的认识。

既然我们得到了差分的幂法则，逆差分中的幂法则也就呼之欲出了： \[ \sum x^{\underline m} \mathrm{\delta} x = \frac{x^{\underline{m+1}}}{m+1}+C,\quad m\in\mathbb{Z}, m\neq -1 \] 这些法则有什么用呢？我们先试试看用我们的方法推导等差数列求和公式吧！

欲求式为 \[ S_n = \sum_{x=1}^n [a_1+(x-1)d] \] 那么我们计算： \[ \begin{aligned} \sum [a_1+(x-1)d]\mathrm{\delta} x &= \sum[a_1-d+dx]\mathrm{\delta} x \\ &= \sum(a_1 - d)\mathrm{\delta} x+\sum dx\mathrm{\delta} x \\ &= (a_1-d)x + d\sum x^{\underline 1} \delta x \\ &= (a_1-d)x + d\cdot\frac{x^{\underline 2}}{2} + C \end{aligned} \] 然后根据之前提到的步骤分别代入 \(x=1\) 和 \(x=n+1\) 作差相减，就是答案： \[ \begin{aligned} \sum_{x=1}^n [a_1+(x-1)d] &= \left[(a_1-d)(n+1)+d\cdot\frac{(n+1)^{\underline 2}}{2}\right] - \left[(a_1 - d)\cdot 1 + d\cdot\frac{1^{\underline 2}}{2} \right] \\ &= (a_1-d)n + \frac{n(n+1)}{2}d \\ &= na_1+\frac{n(n-1)}{2}d \end{aligned} \] 是不是很简单？再比如说我们要求平方和 \[ \sum_{x=1}^n x^2 \] 然后我们发现 \[ x^2 = x^{\underline 2} + x^{\underline 1} \] 那我们可以借此求取 \(x^2\) 的逆差分： \[ \begin{aligned} \sum x^2 \mathrm{\delta} x &= \sum x^{\underline 2}\mathrm{\delta} x + \sum x^{\underline 1}\mathrm{\delta} x \\ &= \frac{x^{\underline 3}}{3} + \frac{x^{\underline 2}}{2} + C \\ &= \frac{2x(x - 1)(x - 2) + 3x(x - 1)}{6} + C \\ &= \frac{x(x - 1)(2x - 1)}{6} + C \end{aligned} \]

代入上下界： \[ \begin{aligned} \sum_{x=1}^n x^2 &= \frac{(n+1)[(n+1) - 1][2(n+1) - 1]}{6} - \frac{1(1- 1)(2\cdot1 - 1)}{6} \\ &= \frac{n(n+1)(2n+1)}{6} \end{aligned} \] 我们一不小心就推出了平方和公式？

再来一个： \[ \sum_{x=1}^n \frac{1}{x(x+1)} \] 我们先把它转变成： \[ \sum_{x=0}^{n-1}\frac{1}{(x+1)(x+2)} \] 因为这样凑到了形式： \[ \frac{1}{(x+1)(x+2)} = x^{\underline{-2}} \] 然后用幂法则逆差分： \[ \sum x^{\underline{-2}} \mathrm{\delta} x = \frac{x^{\underline{-1}}}{-1} + C= -\frac{1}{x+1} + C \] 然后代入 \(x=0\) 和 \(x=n\) 相减： \[ \begin{aligned} \sum_{x=0}^{n-1}\frac{1}{(x+1)(x+2)} &= \left(-\frac{1}{n+1}\right) - \left(-\frac{1}{0+1}\right) \\ &= 1-\frac{1}{n+1} \end{aligned} \] 这不就是裂项吗？

其实，通过归纳可以证明，任何整式多项式都可以被表示为若干个下降阶乘幂的线性组合（且方法是显然的）。且裂项公式的另类证明也说明幂法则在指数为负数的时候也可以使用。（对于复杂的分式，我们也可以待定系数拆着做）。

指数法则

自然而然地，我们接下来探究指数函数（包括底数为负数）的差分与逆差分： \[ \frac{\mathrm{\delta} a^{x}}{\mathrm{\delta} x} = a^{x+1}-a^x=(a-1)a^x \] 因此 \[ \sum a^x\mathrm{\delta} x=\frac{a^x}{a-1} + C ,\quad a\neq 1 \] （要验证？再差分一下）

因此 \[ \sum_{x=0}^{n-1}a^x = \frac{a^n}{a-1} - \frac{a^0}{a-1} = \frac{a^n-1}{a-1} ,\quad a\neq 1 \] 啊，是非平凡等比数列的求和公式呢。

刚刚的结论也可以稍作拓展： \[ \begin{aligned} \frac{\mathrm{\delta} a^{x+k}}{\mathrm{\delta} x} &= (a-1)a^{x+k}\\ \sum a^{x+k}\mathrm{\delta} x&=\frac{a^{x+k}}{a-1} + C \end{aligned} \] 同时可以注意下： \[ \frac{\mathrm{\delta} 2^x}{\mathrm{\delta} x} = 2^x, \sum2^x\mathrm{\delta} x=2^x+C \] 这是一个有意思的现象：\(2^x\)（或更为广义来讲，\(2^{x+k}\)）的差分与逆差分等于其自身。这与微积分中 \(e^x\) 的地位是相似的。

分部求和

如果仅有指数法则和幂法则，那么这套方法其实并没有那么优秀（计算的式子我们常规方法也能算啊！）

真正让这套方法威力大幅提升的，是分部求和。

你也许知道分部积分是从微分的积法则变化而来的： \[ \begin {aligned} &\frac{\mathrm{d}f(x)g(x)}{\mathrm{d}x} = f(x)\frac{\mathrm{d}g(x)}{\mathrm{d}x} + g(x)\frac{\mathrm{d}f(x)}{\mathrm{d}x} \\ \Longleftrightarrow& f(x)\frac{\mathrm{d}g(x)}{\mathrm{d}x} = \frac{\mathrm{d}f(x)g(x)}{\mathrm{d}x}- g(x)\frac{\mathrm{d}f(x)}{\mathrm{d}x}\\ \Longleftrightarrow &\int f(x)\mathrm{d}g(x) = f(x)g(x) - \int g(x)\mathrm{d}f(x) \\ \end{aligned} \] （出于统一风格的需要没有用 \(u,v\)，写得繁复了一点）

我们类比着探寻差分下的积法则： \[ \begin{aligned} \frac{\mathrm{\delta} f(x)g(x)}{\mathrm{\delta} x} &= f(x+1)g(x+1) - f(x)g(x) \\ &= f(x+1)g(x+1)-f(x)g(x+1)+f(x)g(x+1)-f(x)g(x) \\ &= f(x)[g(x+1) - g(x)] + g(x+1)[f(x+1)-f(x)] \\ &= f(x)\frac{\mathrm{\delta} g(x)}{\mathrm{\delta} x} + g(x+1)\frac{\mathrm{\delta} f(x)}{\mathrm{\delta} x} \end{aligned} \] 因此 \[ \sum f(x) \mathrm{\delta} g(x) = f(x)g(x)-\sum g(x+1)\mathrm{\delta} f(x) \] (\(\sum f(x) \mathrm{\delta} g(x) = \sum f(x)\frac{\mathrm{\delta} g(x)}{\cancel{\mathrm{\delta} x}} \cancel{\mathrm{\delta} x}\)，虽然不是直接 “约分”，但是是一种简便的记号)

这便是逆差分当中的分部求和方法。

怎么用？

比如说我们要计算： \[ \sum x^22^x \mathrm{\delta} x \] 那么令 \(f(x)=x^2,\frac{\mathrm{\delta} g(x)}{\mathrm{\delta} x} = 2^x \Rightarrow g(x)=2^x\): \[ \begin{aligned} \sum x^22^x \mathrm{\delta} x = \sum x^2 \mathrm{\delta}2^x&=x^22^x- \sum 2^{x+1}\mathrm{\delta} x^2 \\ &= x^22^x- \sum 2^{x+1}(2x+1)\mathrm{\delta} x \\ &= x^22^x - \sum 2^{x+1}\mathrm{\delta} x - 2\sum x2^{x+1}\mathrm{\delta} x \\ &= x^22^x - 2^{x+1} - 4\sum x2^x\mathrm{\delta} x \end{aligned} \] 再来，令 \(f(x) = x,\frac{\mathrm{\delta} g(x)}{\mathrm{\delta} x} = 2^x \Rightarrow g(x)=2^x\)： \[ \begin{aligned} \sum x2^x\mathrm{\delta} x &= x2^x- \sum 2^{x+1} \mathrm{\delta} x \\ &= x2^x - 2^{x+1} + C \\ \end{aligned} \] 代回去： \[ \begin{aligned} \sum x^22^x \mathrm{\delta} x &= x^22^x - 2^{x+1} - 4\left(x2^x - 2^{x+1}\right) + C \\ &=(x^2-4x+6)2^x+C \end{aligned} \] 然后上下界就按需求随意加好了～

（\(g(x)=2^x+C\) 的时候推导还成立吗？要不要考虑呢？）

换元求和

你也许会想

既然我们都把分部积分类比到了分部求和，那么再把换元积分类比到换元求和岂不美哉？

很遗憾，这在通常意义上是不可以的。

为什么？

因为换元积分逆用的是微分的链式法则。

差分有链式法则吗？ \[ \begin{aligned} \frac{\mathrm{\delta} f[g(x)]}{\mathrm{\delta} x} &= f[g(x+1)] - f[g(x)] \\ &\stackrel{?}{=} \left\{f[g(x)+1]-f[g(x)]\right\}[g(x+1)-g(x)] \\ &= \frac{\mathrm{\delta} f[g(x)]}{\mathrm{\delta} g(x)} \cdot \frac{\mathrm{\delta} g(x)}{\mathrm{\delta} x} \end{aligned} \] 打问号的那一步是推不过来的，除非 \(g(x+1)=g(x)+1 \Longleftrightarrow \frac{\mathrm{\delta} g(x)}{\mathrm{\delta} x} = 1\)。在这种特例条件下，\(g(x)=x+C\)，也就是说我们只能在这样形式的 \(g(x)\) 上应用链式法则 / 换元求和 —— 这个形式不就是平移吗？

而在其他形式的 \(g(x)\) 当中，正如我们所看到的一样，推不过去。

其实，我们没有必要将所有微积分里面的要素全部类比到我们的体系里面。比如说，微分的链式法则与商法则之所以必要是因为微分按照定义计算十分繁琐，而差分的定义本身就可以用来进行计算，因而不需要链式法则与商法则。类似地，微积分里面一些关于三角的技巧也不用，也不能类比到我们的框架当中，因为在离散的情况很难对待三角。

小结

这篇文章给大家分享了一整套可以用来机械化一部分求和计算的方法，并在此方法框架内推导了我们所学过的许多求和公式。这个方法精彩且难能可贵的是，这个方法完全是借助于类比的思想借鉴微积分体系建立起来的。因而如果同学们有关于微积分的了解，那么会发现知识的迁移可以很快完成。这种类比的方法是我们数学学习过程中应该提倡的。

这套方法有名字吗？

《具体数学》当中称该方法为 “有限微积分”，我个人认为 “离散微积分” 更为恰当，但是既然是离散的，那么 “微” 和 “积” 自然无从说起，我个人一直想回避给这个方法命名（就是一个微积分的类比又不是什么开拓性创新有啥好命名的）。

考试 / 作业可以用吗？

我觉得肯定是不行的。首先我确信考试或者作业大概率不会出这种求和。其次我确定很多人并没有听说过这个方法。再其次这套方法和其他技巧还不大一样，是成体系的，所以如果你要用也要像这篇文章一样从头开始定义差分写一大堆。然而如果真的碰到了这样的题目，你当然…… 可以…… 在草稿纸上…… 假装是灵光一闪得到答案…… 然后归纳证明对吧…… 我觉得老师大概也不会拿你怎么样？

调和级数与自然对数

这里只是对于幂法则的一个简要补充，可以跳过。

你也许注意到，正如积分的幂法则一样，我们逆差分的幂法则规定指数不能为 \(-1\)。原因显然。

那指数 \(-1\) 怎么办呢？

你也许知道 \[ \int_1^n x^{-1}\mathrm{d}x=\ln n \] 那类比着不妨看看 \[ \sum_{x=0}^{n-1} x^{\underline{-1}} = \frac{1}{1}+\frac{1}{2}+\cdots+\frac{1}{n}=? \] 这不是调和级数吗？这和 \(\ln n\) 看起来一点都不像啊！然而，可以证明， \[ \lim_{n\to\infty} \left(- \ln n + \sum_{x=1}^n \frac{1}{x}\right) = \gamma \approx 0.57722 \] \(\gamma\) 被称作欧拉 - 马歇罗尼常数。当然这和这篇文章的主题已经一点关系都没有了，权当是对于指数为 \(-1\) 情况的探究与补全吧。

Bonus

暑假里刷计算机竞赛的时候小马碰到一道神奇的数列题。当时所有人都是打表找规律做的（计算机竞赛日常，你写出程序就行），但是我一直很好奇有没有严谨的推导。数列是这个样子的： \[ \begin{aligned} a_1 &= 1 \\ a_n &= \left(\sum_{i=1}^{n-1} i\cdot a_i\right) \bmod n ,\quad n\ge2, n\in \mathbb{N^{\ast}} \end{aligned} \] 求 \(a_n\) 的通项公式。我趁这篇文章的机会问问各位大佬有没有想法，有的话可以和我分享一下。