2 和式 SUMS

数学中处处都有和式，所以我们需要一些基本的工具来处理它们。这一章要建立一些记号和一般性的技巧，使得求和简单易行。

2.1 记号 NOTATION

我们在第 1 章遇到了前 $n$ 个整数的和，把它记为 $1+2+3+\cdots+(n-1)+n$。公式中的 “$\cdots$” 告诉我们，要完整地计算包含的项所确定的模式。当然，我们还得注意像 $1+7+\cdots+41.7$ 这样的和式，如果没有释疑的上下文，它就没有意义。另一方面，包含 $3$ 和 $(n-1)$ 这样的项也有点矫枉过正，如果我们直接写成 $1+2+\cdots+n$，这一模式就可以认为是表述清楚了。有时我们甚至会大胆地写成 $1+\cdots+n$。

我们将研究一般形式的和 $$ a_1+a_2+\cdots+a_n~,\tag{2.1} $$ 其中每个 $a_k$ 都是用某种方式定义的一个数。这一记号的优点是，如果我们有足够好的想象力，就可以 “看见” 整个和，就像能把它完整地写出来一样。

和式的每个元素 $a_k$ 称为项（term）。项常常隐含作为遵循一种容易领会的模式的公式，在这样的情形下，我们有时必须把它们写成展开的形式，以使得其意义清楚明白。例如，如果设想

一学期（term）就是学习这门课程持续的时间。

$$ 1+2+\cdots+2^{n-1} $$ 表示 $n$ 项之和，而不是 $2^{n-1}$ 项之和，我们就应该更明确地把它写成 $$ 2^0+2^1+\cdots+2^{n-1}~. $$ 这个三点记号 ”$\cdots$“ 有多种用途，不过它有可能含糊不清且有点冗长累赘。还可用其他方式，尤其是有确定界限的表达形式 $$ \sum_{k=1}^na_k~,\tag{2.2} $$

”符号 $\sum_{i=1}^{i=\infty}$ 表示应该让整数 $i$ 取遍所有的值 $1,2,3,\cdots$，并且求这些项之和。“ ——J. 傅里叶

它称为 $\Sigma$ 符号，因为用到希腊字母 $\Sigma$（大写的 $\sigma$）。这个记号告诉我们，这个和式中正好包含其指标 $k$ 取介于下限 $1$ 和上限 $n$ 之间（上下限包含在内）的整数的那些项 $a_k$。换句话说，我们 “对 $k$ 从 $1$ 到 $n$ 求和”。约瑟夫 · 傅里叶于 1820 年引入了这个有确定界限的 $\Sigma$ 符号，它随即风靡整个数学界。

附带提及，$\Sigma$ 后面的量（在这里是 $a_k$）称为被加数（summand）。

指标变量 $k$ 被认为是与式 $(2.2)$ 中的 $\Sigma$ 符号密切相关的，因为 $a_k$ 中的 $k$ 与 $\Sigma$ 符号外出现的 $k$ 无关。任何其他字母都可以替代这里的 $k$ 而不会改变 $(2.2)$ 的含义。常常会使用字母 $i$【似乎是因为它代表了 “指标”（index）】，不过我们一般还是对 $k$ 求和，因为 $i$ 另有重任要表示 $\sqrt{-1}$。

是的，我不想用 $a$ 或者 $n$ 来替代式 $(2.2)$ 中的 $k$ 作为指标变量，那些字母是 ”自由变量“，它们在 $\Sigma$ 之外是有意义的。

现在已经明白，一种推广的 $\Sigma$ 符号甚至要比有确定界限的形式更加有用：我们直接把一个或者多个条件写在 $\Sigma$ 的下面，以此指定求和所应该取的指标集。例如，$(2.1)$ 和 $(2.2)$ 中的和式也可以写成 $$ \sum_{1\leqslant k\leqslant n}a_k~.\tag{2.3} $$ 在这个特殊的例子中，新的形式与 $(2.2)$ 没有太大区别，但是一般形式的和允许我们对不限于连续整数的指标求和。例如，我们可以将不超过 $100$ 的所有正奇数的平方和表示为 $$ \sum_{\substack{1\leqslant k<100\\[0.5ex]k\text{是奇数}}}k^2~. $$ 而这个和式有确定界限的等价形式 $$ \sum_{k=0}^{49}(2k+1)^2 $$ 要更加繁琐不便，且不清晰。类似地，$1$ 与 $N$ 之间所有素数的倒数之和是 $$ \sum_{\substack{p\leqslant N\\[0.5ex]p\text{是素数}}}\frac1p~; $$ 而有确定界限的形式则需要写成 $$ \sum_{k=1}^{\pi(N)}\frac1{p_k}~, $$ 其中 $p_k$ 表示第 $k$ 个素数，$\pi(N)$ 是 $\leqslant N$ 的素数个数。（附带指出，这个和式给出了接近 $N$ 的随机整数的不同素因子的近似平均个数，因为那些整数中大约有 $1/p$ 个能被 $p$ 整除。对于大的 $N$，它的值近似等于 $\ln\ln N+M$，其中 $$ M\approx0.261~497~212~847~642~783~755~426~838~608~695~859~051~566~6 $$ 是麦尔滕常数，$\ln x$ 表示 $x$ 的自然对数，而 $\ln\ln x$ 表示 $\ln(\ln x)$。）

一般 $\Sigma$ 符号的最大好处是比有确定界限的形式更容易处理。例如，假设要将指标变量 $k$ 改变成 $k+1$。由一般形式，我们就有

求和符号看起来像一个扭曲的吃豆人。

《吃豆人》（pacman）是 Namco 公司于 1980 年推出的一款经典游戏，目前仍是 Namco 的看家游戏之一。此款游戏的制作人是岩谷彻，Namco 的前身是由中村雅哉于 1955 年创立的中村制作所于 1977 年更名而来。

$$ \sum_{1\leqslant k\leqslant n}a_k=\sum_{1\leqslant k+1\leqslant n}a_{k+1}~; $$ 很容易看出所做的变动，我们几乎不需要思考就能做出这样的代换。但是对于有确定界限的形式，就有 $$ \sum_{k=1}^na_k=\sum_{k=0}^{n-1}a_{k+1}~; $$ 不容易看出它发生了什么变化，而且更容易犯错误。

另一方面，有确定界限的形式也并非完全没有用。它漂亮而且简洁，相比较而言，由于 $(2.2)$ 有 7 个符号而 $(2.3)$ 有 8 个符号，故而可以很快写出式 $(2.2)$。因此，当我们要陈述一个问题或者表述一个结论时，常会使用带有上下确定界限的 $\Sigma$，而当处理一个需要对指标变量做变换的和式时，则更愿意用在 $\Sigma$ 下方列出关系的形式。

一个整齐的和式。

在这本书中，符号 $\Sigma$ 要出现 1000 多次，所以我们要确信自己已经明确知道了它的含义，形式上，我们将

这没有什么。你应该看看在《伊利亚特》中 $\Sigma$ 出现了多少次。

$$ \sum_{P(k)}a_k\tag{2.4} $$ 记为所有项 $a_k$ 之和的缩写，其中的 $k$ 是满足给定性质 $P(k)$ 的一个整数。（“性质 $P(k)$” 是关于 $k$ 的任何一个为真或者为假的命题。）我们暂时假定仅有有限多个满足 $P(k)$ 的整数 $k$ 使得 $a_k\ne0$；反之则有无穷多个非零的数相加，事情就会有点儿复杂。在另一种极端情形，如果对所有的整数 $k$，$P(k)$ 都不为真，我们就有一个 “空的” 和，任何空的和的值都定义为零。

当一个和式出现在正文而不是给出的方程中时，就用一个对 $(2.4)$ 稍加修改的形式写成 $\sum_{P(k)}a_k$，将性质 $P(k)$ 作为 $\Sigma$ 的下标，从而使得公式不会太突出。类似地，当我们希望将记号限制在一行里的时候，$\sum_{k=1}^na_k$ 就是 $(2.2)$ 的另一种便于应用的选择。

人们常常想要使用 $$ \sum_{k=2}^{n-1}k(k-1)(n-k)~, $$ 而不是 $$ \sum_{k=0}^nk(k-1)(n-k)~. $$ 因为在这个和式中 $k=0,1$ 以及 $n$ 的项都等于零。将 $n-2$ 项相加而不是将 $n+1$ 项相加往往更为有效。但是不应该这样想，因为计算的有效性并不等同于理解的有效性！我们会发现，保持求和指标的上下限尽可能简单大有裨益，因为当求和的界限简单时，处理起来要容易得多。的确，形式 $\sum_{k=2}^{n-1}$ 会有含糊不清的风险，因为当 $n=0$ 或者 $n=1$ 时，它的含义根本就不清晰（见习题 1）。取零值的项不会带来问题，反而常会免除许多麻烦。

到目前为止，我们讨论的记号都相当标准，不过现在我们要与惯用法彻底告别了。肯尼斯 · 艾弗森在他的程序语言 APL 中引入了一个奇妙的思想，我们将会看到，这一思想将会极大地简化我们在这本书里想要做的许多事情。这一思想仅仅包含一个含在括号中的为真或为假的命题，其结果是 $1$（如果该命题为真），或结果是为 $0$（如果该命题为假）。例如，

嘿：我在其他书中看到的 Kronecker $\delta$（我指的是 $\delta_{kn}$，当 $k=n$ 时它为 $1$，反之则为 $0$）恰好是艾弗森约定的一种特殊情形。我们可以写成 $[k=n]$ 替代之。

$$ [p\text{ 是素数}]=\begin{cases}1~,&p\text{ 是素数；}\\0~,&p\text{ 不是素数。}\end{cases} $$ 无论对求和指标有何种要求，艾弗森约定都使得我们可以不加限制条件来表示和式，把 $(2.4)$ 重新写成形式 $$ \sum_ka_k[P(k)]\tag{2.5} $$ 如果 $P(k)$ 为假，那么项 $a_k[P(k)]$ 等于零，所以我们可以安全地将它包含在要求和的各项之中。因为不会由于边界条件而受到干扰，我们可以容易地处理求和指标。

“我常常对（这个记号）新的重要应用惊讶不已。” ——布鲁诺 · 德 · 费奈蒂

有必要提及一点技术上的细节：有时 $a_k$ 并非对所有整数 $k$ 定义。当 $P(k)$ 为假时，我们假设 $[P(k)]$ “必定是零” 来规避这个困难，它就是零，甚至 $a_k$ 无定义时 $a_k[P(k)]$ 也等于零。例如，如果用艾弗森约定将 $\leqslant N$ 的素数倒数之和写成 $$ \sum_p[p\text{ 是素数}][p\leqslant N]/p~, $$ 当 $p=0$ 时就不会存在用零做除数的问题，因为约定告诉我们 $[0\text{ 是素数}][0\leqslant N]/0=0$。

我们来对到目前为止关于和式的讨论做个总结。有两种好的方法来表达诸项之和。一种方法利用 “$\cdots$”，另一种方法利用 $\Sigma$。三点形式常提示有用的操作，特别是相邻项的组合方式，因为如果整个和式挂在我们眼前，我们或许能想出一个简化模式。但是，太多的细节也有可能会让人手足无措，$\Sigma$ 符号既紧凑，又能让人印象深刻，而且常常能给出三点形式所不明显具有的操作提示。当我们处理 $\Sigma$ 符号时，为零的项一般不会有问题，事实上，零常常使得对 $\Sigma$ 的处理更加容易。

“$\cdots$” 在考试中不太会由于 “缺乏严格性” 而丢分。

2.2 和式和递归式 SUMS AND RECURRENCES

好了，现在我们知道如何用特定的符号表示和式了。那又该如何来求和式的值呢？一种方法是观察和式与递归式之间存在的密切关系。和式 $$ S_n=\sum_{k=0}^na_k $$

（不把 $S_n$ 看成仅仅是一个单独的数，而将它看成是一个对所有 $n\geqslant0$ 都有定义的序列。）

等价于递归式 $$ \begin{aligned}S_0&=a_0~;\\S_n&=S_{n-1}+a_n~,\quad n>0~.\end{aligned}\tag{2.6} $$ 这样一来，利用在第 1 章里学到的用封闭形式求解递归式的方法，我们就可以用封闭形式计算和式的值。

例如，如果 $a_n$ 等于一个常数加上 $n$ 的一个倍数，那么和式—递归式 $(2.6)$ 的一般形式犹如 $$ \begin{aligned}R_0&=\alpha~;\\R_n&=R_{n-1}+\beta+\gamma n~,\quad n>0~.\end{aligned}\tag{2.7} $$ 如同在第 1 章里那样，我们求得 $R_1=\alpha+\beta+\gamma$，$R_2=\alpha+2\beta+3\gamma$ 等，一般来说，它的解可以写成形式 $$ R_n=A(n)\alpha+B(n)\beta+C(n)\gamma~,\tag{2.8} $$ 其中 $A(n)$、$B(n)$ 和 $C(n)$ 是系数，它们依赖于一般的参数 $\alpha$、$\beta$ 和 $\gamma$。

使用成套方法，用 $n$ 的简单函数来替代 $R_n$，希望能求出常数参数 $\alpha$、$\beta$ 和 $\gamma$，其中的解特别简单。令 $R_n=1$ 就意味着 $\alpha=1$，$\beta=0$，$\gamma=0$，从而 $$ A(n)=1~. $$ 令 $R_n=n$ 就意味着 $\alpha=0$，$\beta=1$，$\gamma=0$，从而 $$ B(n)=n~. $$ 令 $R_n=n^2$ 就意味着 $\alpha=0$，$\beta=-1$，$\gamma=2$，从而 $$ 2C(n)-B(n)=n^2 $$ 且有 $C(n)=(n^2+n)/2$。容易之极。

实际上更容易，$\pi=\sum_{n\geqslant0}\dfrac8{(4n+1)(4n+3)}$

于是，如果我们想要计算 $$ \sum_{k=0}^n(a+bk)~, $$ 则和式—递归式 $(2.6)$ 就转化成了 $(2.7)$，其中 $\alpha=\beta=a$，$\gamma=b$，而答案是 $$ aA(n)+aB(n)+bC(n)=a(n+1)+b(n+1)n/2~. $$ 反过来，许多递归式都可以转化成为和式，所以，我们将在本章后面学习如何计算和式的特殊方法，这会帮助我们求解递归式，否则求解这些递归式有可能会很困难。河内塔递归式就是一个恰当的例子： $$ \begin{aligned}T_0&=0~;\\T_n&=2T_{n-1}+1~,\quad n>0~.\end{aligned} $$ 如果两边都用 $2^n$ 来除，它可以写成特殊的形式 $(2.6)$： $$ \begin{aligned}T_0/2^0&=0~;\\T_n/2^n&=T_{n-1}/2^{n-1}+1/2^n~,\quad n>0~.\end{aligned} $$ 现在令 $S_n=T_n/2^n$，我们就有 $$ \begin{aligned}S_0&=0~;\\S_n&=S_{n-1}+2^{-n}~,\quad n>0~.\end{aligned} $$ 由此得到 $$ S_n=\sum_{k=1}^n2^{-k}~. $$ （注意，和式中舍弃了 $k=0$ 的项。）几何级数的和 $$ 2^{-1}+2^{-2}+\cdots+2^{-n}=\left(\frac12\right)^1+\left(\frac12\right)^2+\cdots+\left(\frac12\right)^n $$ 将在本章的后部加以推导，可以证明它等于 $1-\left(\dfrac12\right)^n$，故而 $T_n=2^nS_n=2^n-1$。

注意此递归式可以用 $2^n$ 来除，从而在这一推导过程中我们将 $T_n$ 转换成了 $S_n$。这一技巧是一般技术的一个特殊情形，实际上一般技术可以将任何形如 $$ a_nT_n=b_nT_{n-1}+c_n\tag{2.9} $$ 的递归式转化成一个和式。其思想在于用一个**求和因子**（summation factor）$s_n$ 来乘两边： $$ s_na_nT_n=s_nb_nT_{n-1}+s_nc_n~. $$ 因子 $s_n$ 需要恰当地选取，以使得 $$ s_nb_n=s_{n-1}a_{n-1}~. $$ 这样一来，如果记 $S_n=s_na_nT_n$，我们就得到一个和式—递归式 $$ S_n=S_{n-1}+s_nc_n~. $$ 从而 $$ S_n=s_0a_0T_0+\sum_{k=1}^ns_kc_k=s_1b_1T_0+\sum_{k=1}^ns_kc_k~, $$ 而原来的递归式 $(2.9)$ 的解就是 $$ T_n=\frac1{s_na_n}\left(s_1b_1T_0+\sum_{k=1}^ns_kc_k\right).\tag{2.10} $$ 例如，当 $n=1$ 时得到 $T_1=(s_1b_1T_0+s_1c_1)/s_1a_1=(b_1T_0+c_1)/a_1$。

（$s_1$ 的值消去了，所以它可以是除零以外的任何数。）

但是，我们怎样才能有足够的智慧求出正确的 $s_n$ 呢？没有问题：关系式 $s_n=s_{n-1}a_{n-1}/b_n$ 可以被展开，从而我们发现，分式 $$ s_n=\frac{a_{n-1}a_{n-2}\cdots a_1}{b_nb_{n-1}\cdots b_2}\tag{2.11} $$ 或者这个值的任何适当的常数倍，会是一个合适的求和因子。例如，河内塔递归式有 $a_n=1$ 和 $b_n=2$，由刚刚推导出来的一般方法可知，如果要把递归式转化为和式，那么 $s_n=2^{-n}$ 就是一个用来相乘的好东西。发现这个乘数并不需要闪光的思想灵感。

我们必须小心谨慎，永远不用 $0$ 做除数。只要所有的 $a$ 和所有的 $b$ 都不为零，那么求和因子方法就能奏效。

我们来把这些想法应用到 “快速排序” 研究中所出现的递归式，快速排序是计算机内部数据排序的一种最重要的方法。当把它应用到有 $n$ 个随机排列的项目时，用典型的快速排序方法所做的比较步骤的平均次数满足递归式

（快速排序是霍尔在 1962 年发明的。）

$$ \begin{aligned}C_0&=C_1=0~;\\C_n&=n+1+\frac2n\sum_{k=0}^{n-1}C_k~,\quad n>1~.\end{aligned}\tag{2.12} $$ 嗯。这看起来比我们以前见过的递归式要可怕得多，它包含一个对前面所有值求和的和式，且还要除以 $n$。尝试小的情形，我们得到一些数据（$C_2=3$，$C_3=6$，$C_4=\dfrac{19}2$），但这对消除我们的畏难情绪并没有任何作用。

然而，我们可以系统地来化解 $(2.12)$ 的复杂性，首先避免除法，然后再规避掉符号 $\Sigma$。想法是用 $n$ 来乘两边，这就得到关系式 $$ nC_n=n^2+n+2\sum_{k=0}^{n-1}C_k~,\quad n>1~, $$ 于是，如果我们用 $n-1$ 代替 $n$，就有 $$ (n-1)C_{n-1}=(n-1)^2+(n-1)+2\sum_{k=0}^{n-2}C_k~,\quad n-1>1~. $$ 现在可以从第一个方程中减去这个方程，求和号就消失了： $$ nC_n-(n-1)C_{n-1}=2n+2C_{n-1}~,\quad n>2~. $$ 这样一来，原来关于 $C_n$ 的递归式就转化为一个简单得多的递归式： $$ \begin{aligned}C_0&=C_1=0~;\quad C_2=3~;\\nC_n&=(n+1)C_{n-1}+2n~,\quad n>2~.\end{aligned} $$ 进了一步。由于这个递归式形如 $(2.9)$，其中 $a_n=n$，$b_n=n+1$，且 $$ c_n=2n-2[n=1]+2[n=2]~, $$ 故而我们现在能用求和因子方法。前面描述的一般方法告诉我们，要用 $$ s_n=\frac{a_{n-1}a_{n-2}\cdots a_1}{b_nb_{n-1}\cdots b_2}=\frac{(n-1)\times(n-2)\times\cdots\times1}{(n+1)\times n\times\cdots\times3}=\frac2{(n+1)n} $$ 的某个倍数来遍乘该递归式。根据 $(2.10)$，它的解就是 $$ C_n=2(n+1)\sum_{k=1}^n\frac1{k+1}-\frac23(n+1)~,\quad n>1~. $$

我们从递归式中的 $\Sigma$ 开始，并且努力规避它。但在应用求和因子之后，我们又与另一个 $\Sigma$ 不期而遇。和式究竟是好，是坏，抑或是其他的什么？

最后出现的这个和式与应用中频繁出现的一个量颇为相似。事实上，因为它出现得如此频繁，我们将给它一个特殊的名称和一个特别的记号： $$ H_n=1+\frac12+\cdots+\frac1n=\sum_{k=1}^n\frac1k~.\tag{2.13} $$ 字母 $H$ 表示 “调和的”，$H_n$ 称为一个**调和数**（harmonic number）。之所以这样命名，是因为小提琴弦所产生的第 $k$ 个`泛音`（harmonic）是弦长 $1/k$ 处所产生的基音。

我们可以通过将 $C_n$ 表示为封闭形式来研究快速排序递归式 $(2.12)$。如果我们能用 $H_n$ 来表示 $C_n$，这就将是可能的。$C_n$ 公式中的和式是 $$ \sum_{k=1}^n\frac1{k+1}=\sum_{1\leqslant k\leqslant n}\frac1{k+1}~. $$ 将 $k$ 改为 $k-1$ 并修改边界条件，我们可以毫不费力地把它与 $H_n$ 联系起来： $$ \begin{aligned}\sum_{1\leqslant k\leqslant n}\frac1{k+1}&=\sum_{1\leqslant k-1\leqslant n}\frac1k\\&=\sum_{2\leqslant k\leqslant n+1}\frac1k\\&=\left(\sum_{1\leqslant k\leqslant n}\frac1k\right)-\frac11+\frac1{n+1}=H_n-\frac n{n+1}~.\end{aligned} $$ 好的（alright）！我们已经发现了求解 $(2.12)$ 所需要的和：当它被应用到有 $n$ 个随机排列的数据项时，用快速排序方法做比较的平均次数是

但是你的拼写全错了（alwrong）。

正文中 “好的” 一词用的是不规范的单词 alright，这里 “全错了” 用的也是不规范单词 alwrong，以相映成趣。

$$ C_n=2(n+1)H_n-\frac83n-\frac23~,\quad n>1~.\tag{2.14} $$

如通常一样，我们验证小的情形是正确的：$C_2=3$，$C_3=6$。

2.3 和式的处理 MANIPULATION OF SUMS

不要和金融搞混了。

“和式” 的英文词 sum 还有总金额这一金融学的含义，故作者对这一节的标题由此一说。

成功处理和式的关键在于，将一个 $\Sigma$ 改变成另一个更简单或者更接近某个目标的 $\Sigma$。通过学习一些基本的变换法则并在实践中练习使用它们，就会容易做到这点。

设 $K$ 是任意一个有限整数集合。$K$ 中元素的和式可以用三条简单的法则加以变换： $$ \begin{align}\sum_{k\in K}ca_k&=c\sum_{k\in K}a_k~;&\text{（分配律）}\tag{2.15}\\\sum_{k\in K}(a_k+b_k)&=\sum_{k\in K}a_k+\sum_{k\in K}b_k~;&\text{（结合律）}\tag{2.16}\\\sum_{k\in K}a_k&=\sum_{p(k)\in K}a_{p(k)}~.&\text{（交换律）}\tag{2.17}\end{align} $$

我的其他数学书对这些法则有不同的定义。

的确，尤其是这里定义的分配律和结合律，与通常数学书中这两个定律的定义有很大区别。

运用分配律，我们能把常数移入和移出 $\Sigma$；运用结合律，我们可以把一个 $\Sigma$ 分成两个部分，或者将两个 $\Sigma$ 组合成一个；运用交换（commutative）律，我们可以按照愿意采用的任何方法来重新将求和项排序，这里 $p(k)$ 是所有整数集合的任意一个排列（permutation）。例如，如果 $K=\{-1,0,+1\}$ 且 $p(k)=-k$，那么运用这三条法则就有

为什么不把它称为 permutative，而称为 commutative 呢？

英语词典中没有 permutative 这个词，而与 commutative 意思相近的另一个单词是 permutable。

$$ \def\arraystretch{1.25}\begin{array}{l}ca_{-1}+ca_0+ca_1=c(a_{-1}+a_0+a_1)~,\text{（分配律）}\\(a_{-1}+b_{-1})+(a_0+b_0)+(a_1+b_1)=(a_{-1}+a_0+a_1)+(b_{-1}+b_0+b_1)~,\text{（结合律）}\\a_{-1}+a_0+a_1=a_1+a_0+a_{-1}~.\text{（交换律）}\end{array} $$ 第 1 章里高斯的技巧可以看成是这三条基本法则的一个应用。假设我们要计算一个**等差级数**（arithmetic progression）的一般和 $$ S=\sum_{0\leqslant k\leqslant n}(a+bk)~. $$ 根据交换律，我们可以用 $n-k$ 代替 $k$，得到 $$ S=\sum_{0\leqslant n-k\leqslant n}\big(a+b(n-k)\big)=\sum_{0\leqslant k\leqslant n}(a+bn-bk)~. $$

这有点像在积分号内做变量代换，不过更加容易。

利用结合律，可以把这两个方程相加 $$ 2S=\sum_{0\leqslant k\leqslant n}\big((a+bk)+(a+bn-bk)\big)=\sum_{0\leqslant k\leqslant n}(2a+bn)~. $$ 现在利用分配律，来计算平凡的和式： $$ 2S=(2a+bn)\sum_{0\leqslant k\leqslant n}1=(2a+bn)(n+1)~. $$

“1 加 1 加 1 加 1 加 1 加 1 加 1 加 1 加 1 加 1 等于多少？”
“我不知道，” Alice 说，“我算糊涂了。”“她不会做加法。” ——刘易斯 · 卡罗尔

用 $2$ 除，我们就证明了 $$ \sum_{k=0}^n(a+bk)=\left(a+\frac12bn\right)(n+1)~.\tag{2.18} $$ 右边可以看成是第一项和最后一项的平均值（即 $\dfrac12\big(a+(a+bn)\big)$）乘以项数（即 $(n+1)$）。

重要的是要记住，在一般的交换律 $(2.17)$ 中的函数 $p(k)$ 都假设是所有整数的排列。换句话说，对每个整数 $n$，都恰好存在一个整数 $k$，使得 $p(k)=n$。否则交换律可能不成立，习题 3 就以极端的方式对此做了描述。像 $p(k)=k+c$ 或者 $p(k)=c-k$（其中 $c$ 是一个整数常数）这样的变换总是排列，故而它们总能奏效。

另一方面，我们能将排列限制稍微放松一点点：我们只需要求，当 $n$ 是指标集 $K$ 的一个元素时，恰好有一个整数 $k$ 满足 $p(k)=n$。如果 $n\notin K$（也就是说，如果 $n$ 不在 $K$ 中），那么不管 $p(k)=n$ 以怎样的频率出现都无关紧要，因为这样的 $k$ 不出现在此和式中。例如，由于 $n\in K$ 且 $n$ 是偶数时恰好有一个 $k$ 使得 $2k=n$，故而我们可以主张 $$ \sum_{\substack{k\in K\\[0.5ex]k\text{是偶数}}}a_k=\sum_{\substack{n\in K\\[0.5ex]n\text{是偶数}}}a_n=\sum_{\substack{2k\in K\\[0.5ex]2k\text{是偶数}}}a_{2k}=\sum_{2k\in K}a_{2k}~.\tag{2.19} $$ 通过公式中间的逻辑命题来得到 $0$ 或者 $1$ 的艾弗森判定，可以与分配律、结合律以及交换律一起使用，以导出和式的其他性质。例如，下面是将不同的指标集组合在一起的一个重要法则：如果 $K$ 和 $K'$ 是整数的任意集合，那么

其他的（additional），呃？

$$ \sum_{k\in K}a_k+\sum_{k\in K'}a_k=\sum_{k\in K\cap K'}a_k+\sum_{k\in K\cup K'}a_k~.\tag{2.20} $$ 这是由一般的公式 $$ \sum_{k\in K}a_k=\sum_ka_k[k\in K]\tag{2.21} $$ 和 $$ [k\in K]+[k\in K']=[k\in K\cap K']+[k\in K\cup K']\tag{2.22} $$ 推出的。如同在 $$ \sum_{k=1}^ma_k+\sum_{k=m}^na_k=a_m+\sum_{k=1}^na_k~,\quad1\leqslant m\leqslant n $$

中那样，利用法则 $(2.20)$ 把两个几乎不相交的指标集合并起来，或者像在 $$ \sum_{0\leqslant k\leqslant n}a_k=a_0+\sum_{1\leqslant k\leqslant n}a_k~,\quad n\geqslant0\tag{2.23} $$

（这里交换了 $(2.20)$ 的两边。）

中那样，把单独一项从和式中分出去。

把一项分出去的运算是扰动法（perburbation method）的基础，利用扰动法，我们常常可以用封闭形式来计算一个和式。其思想是从一个未知的和式开始，并记它为 $S_n$： $$ S_n=\sum_{0\leqslant k\leqslant n}a_k~. $$ （命名并求解。）然后，通过将它的最后一项和第一项分离出来，用两种方法重新改写 $S_{n+1}$： $$ \begin{align}S_n+a_{n+1}=\sum_{0\leqslant k\leqslant n+1}a_k&=a_0+\sum_{1\leqslant k\leqslant n+1}a_k\notag\\&=a_0+\sum_{1\leqslant k+1\leqslant n+1}a_{k+1}\notag\\&=a_0+\sum_{0\leqslant k\leqslant n}a_{k+1}\tag{2.24}\end{align} $$ 现在我们可以对最后那个和式加以处理，并尝试用 $S_n$ 将它表示出来。如果取得成功，我们就得到一个方程，它的解就是我们所求的和式。

例如，我们用这个方法来求一般的几何级数（geometric progression）的和

如果它是几何的，就应该有一个几何的证明。
（此处省略一张图）
啊，是的，这个公式在中学时就已经反复背诵了。

$$ S_n=\sum_{0\leqslant k\leqslant n}ax^k~. $$ 由 $(2.24)$ 中一般的扰动法格式，我们有 $$ S_n+ax^{n+1}=ax^0+\sum_{0\leqslant k\leqslant n}ax^{k+1}~, $$ 根据分配律，右边的和式等于 $x\sum_{0\leqslant k\leqslant n}ax^k=xS_n$。于是，$S_n+ax^{n+1}=a+xS_n$，我们可以对 $S_n$ 求解，得到 $$ \sum_{k=0}^nax^k=\frac{a-ax^{n+1}}{1-x}~,\quad x\ne1~.\tag{2.25} $$ （当 $x=1$ 时，这个和当然就直接等于 $(n+1)a$。）右边可以视为和式中的第一项减去在此级数之外的第一项（级数最后一项的后面一项），再除以 $1$ 减去公比。

那几乎太容易了。我们在稍微难一些的和式 $$ S_n=\sum_{0\leqslant k\leqslant n}k2^k $$ 上来尝试使用扰动技术。在此情形下，由 $S_0=0$，$S_1=2$，$S_2=10$，$S_3=34$，$S_4=98$，一般的公式是什么呢？根据 $(2.24)$，有 $$ S_n+(n+1)2^{n+1}=\sum_{0\leqslant k\leqslant n}(k+1)2^{k+1}~, $$ 所以我们想要用 $S_n$ 来表示右边的和式。好的，我们借助结合律将它分成两个和式 $$ \sum_{0\leqslant k\leqslant n}k2^{k+1}+\sum_{0\leqslant k\leqslant n}2^{k+1}~, $$ 剩下和式中的第一个等于 $2S_n$。另一个和式是个几何级数，由 $(2.25)$，它等于 $(2-2^{n+2})/(1-2)=2^{n+2}-2$。于是，我们有 $S_n+(n+1)2^{n+1}=2S_n+2^{n+2}-2$，而通过代数计算就得到 $$ \sum_{0\leqslant k\leqslant n}k2^k=(n-1)2^{n+1}+2~. $$ 现在我们就理解了为什么有 $S_3=34$：它是 $32+2$，而不是 $2\times17$。

用 $x$ 代替 $2$，类似的推导将会给出方程 $S_n+(n+1)x^{n+1}=xS_n+(x-x^{n+2})/(1-x)$，故而我们得出 $$ \sum_{k=0}^nkx^k=\frac{x-(n+1)x^{n+1}+nx^{n+2}}{(1-x)^2}~,\quad x\ne1~.\tag{2.26} $$ 有意思的是，我们可以用一种完全不同的方法，即微积分的初等技巧来推导出这个封闭形式。如果我们从方程 $$ \sum_{k=0}^nx^k=\frac{1-x^{n+1}}{1-x} $$ 开始，并在两边关于 $x$ 求导，就得到 $$ \sum_{k=0}^nkx^{k-1}=\frac{(1-x)\big(\hspace{-0.25em}-\hspace{-0.25em}(n+1)x^n\big)+1-x^{n+1}}{(1-x)^2}=\frac{1-(n+1)x^n+nx^{n+1}}{(1-x)^2}~, $$ 因为和式的导数等于它的各项导数之和。我们将在后续几章中看到微积分与离散数学之间更多的联系。

2.4 多重和式 MULTIPLE SUMS

一个和式的项可以用两个或者更多的指标来指定，而不是仅由一个指标来指定。例如，下面是一个有九项的二重和式，它由两个指标 $j$ 和 $k$ 所掌控：

哦，不，一个九学期（term）的管理者。

$$ \sum_{1\leqslant j,k\leqslant3}a_jb_k=a_1b_1+a_1b_2+a_1b_3+a_2b_1+a_2b_2+a_2b_3+a_3b_1+a_3b_2+a_3b_3~. $$

注意，这并不是说对所有 $j\geqslant1$ 和所有 $k\leqslant3$ 求和。

对这样的和式，我们使用与对单个指标集的和式同样的记号和方法，于是，如果 $P(j,k)$ 是 $j$ 与 $k$ 的一种性质，所有使得 $P(j,k)$ 为真的项 $a_{j,k}$ 之和可以用两种方式表示。一种用艾弗森约定且对所有的整数对 $j$ 与 $k$ 求和： $$ \sum_{P(j,k)}a_{j,k}=\sum_{j,k}a_{j,k}\big[P(j,k)\big]. $$ 它只需要一个符号 $\Sigma$，尽管这里有多于一个求和指标，$\Sigma$ 表示对所有适用的指标组合求和。

当谈论一个和式的和式时，我们有时也会使用两个 $\Sigma$ 符号。例如， $$ \sum_j\sum_ka_{j,k}[P(j,k)] $$ 就是 $$ \sum_j\left(\sum_ka_{j,k}[P(j,k)]\right) $$ 的缩写，这是 $\sum\limits_ka_{j,k}[P(j,k)]$ 对所有整数 $j$ 求和的和式，而 $\sum\limits_ka_{j,k}[P(j,k)]$ 是项 $a_{j,k}$ 对使得 $[P(j,k)]$ 为真的所有整数 $k$ 求和的和式。在这样的情形，我们就说此二重和式 “首先关于 $k$ 求和”。多于一个指标的和式可以首先对它的任何一个指标求和。

多重 $\Sigma$ 从右向左计算（由内而外）。

在这方面，我们有一个称为交换求和次序（interchanginig the order of summation）的基本法则，它推广了我们早先见过的结合律 $(2.16)$： $$ \sum_j\sum_ka_{j,k}[P(j,k)]=\sum_{P(j,k)}a_{j,k}=\sum_k\sum_ja_{j,k}[P(j,k)]~.\tag{2.27} $$ 这一法则的中间项是对两个指标求和的和式。在左边，$\sum_j\sum_k$ 表示先对 $k$ 求和，然后对 $j$ 求和。而在右边，$\sum_k\sum_j$ 表示先对 $j$ 求和，然后对 $k$ 求和。实践中，当我们想用封闭形式计算一个二重和式时，通常先对一个指标求和会比先对另一个指标求和更容易些，所以我们要选取那种更加方便的求和顺序。

不必对和式的和式感到紧张，不过它们可能会让初学者费解，所以我们来多举几个例子。开始给出的九个项的和式是处理二重和式的一个很好的例子，因为那个和式实际上可以简化，而且它的简化程序是我们对 $\Sigma\Sigma$ 所能进行处理的典型代表：

谁紧张啦？我认为这个法则与第 1 章里的某些内容相比，更显而易见一些。

$$ \begin{aligned}\sum_{1\leqslant j,k\leqslant3}a_jb_k&=\sum_{j,k}a_jb_k[1\leqslant j,k\leqslant3]=\sum_{j,k}a_jb_k[1\leqslant j\leqslant3][1\leqslant k\leqslant3]\\&=\sum_j\sum_ka_jb_k[1\leqslant j\leqslant3][1\leqslant k\leqslant3]\\&=\sum_ja_j[1\leqslant j\leqslant3]\sum_kb_k[1\leqslant k\leqslant3]\\&=\sum_ja_j[1\leqslant j\leqslant3]\left(\sum_kb_k[1\leqslant k\leqslant3]\right)\\&=\left(\sum_ja_j[1\leqslant j\leqslant3]\right)\hspace{-0.25em}\left(\sum_kb_k[1\leqslant k\leqslant3]\right)\\&=\left(\sum_{j=1}^3a_j\right)\hspace{-0.25em}\left(\sum_{k=1}^3b_k\right).\end{aligned} $$ 这里的第一行表示没有任何特殊次序的九项之和。第二行把它们分成三组 $$ (a_1b_1+a_1b_2+a_1b_3)+(a_2b_1+a_2b_2+a_2b_3)+(a_3b_1+a_3b_2+a_3b_3)~. $$ 第三行利用分配律提取出诸个因子 $a$，因为 $a_j$ 和 $[1\leqslant j\leqslant3]$ 均与 $k$ 无关，这给出 $$ a_1(b_1+b_2+b_3)+a_2(b_1+b_2+b_3)+a_3(b_1+b_2+b_3)~. $$ 第四行与第三行相同，但是多了一对括号，这样就使得第五行看起来不那么神秘。第五行提取出对 $j$ 的每一个值都出现的因子 $(b_1+b_2+b_3)$：$(a_1+a_2+a_3)(b_1+b_2+b_3)$。而最后一行则是上面一行的另一种表达方式。这一推导方法可以用来证明**一般分配律**（general distributive law） $$ \sum_{\substack{j\in J\\[0.5ex]k\in K}}a_jb_k=\left(\sum_{j\in J}a_j\right)\hspace{-0.25em}\left(\sum_{k\in K}b_k\right),\tag{2.28} $$ 它对所有的指标集 $J$ 和 $K$ 成立。

交换求和顺序的基本法则 $(2.27)$ 有许多变形，这些变形在我们想要限制指标集的范围而不是对所有整数 $j$ 和 $k$ 求和时就会出现。这些变形有两种类型：简易型（vanilla）和复杂型（rocky road）。首先是简易型

书中作者用 vanilla 和 rocky road 这两种风味的冰激淋来比喻简易型和复杂型这两类不同交换求和次序的法则。

$$ \sum_{j\in J}\sum_{k\in K}a_{j,k}=\sum_{\substack{j\in J\\[0.5ex]k\in K}}a_{j,k}=\sum_{k\in K}\sum_{j\in J}a_{j,k}~.\tag{2.29} $$ 这恰好是 $(2.27)$ 的另一种写法，因为艾弗森的 $[j\in J,k\in K]$ 分解成 $[j\in J][k\in K]$。简易风格的法则当 $j$ 和 $k$ 的范围相互无关时适用。

交换的复杂型公式有一点点技巧，它适用于内和的范围与外和的指标变量有关的情形 $$ \sum_{j\in J}\sum_{k\in K(j)}a_{j,k}=\sum_{k\in K'}\sum_{j\in J'(k)}a_{j,k}~.\tag{2.30} $$ 这里的集合 $J$、$K(j)$、$K'$ 与 $J'(k)$ 必须以下面的方式相关联： $$ [j\in J][k\in K(j)]=[k\in K'][j\in J'(k)]~. $$ 原则上，这样的因子分解总是可能的：我们可以设 $J=K'$ 是所有整数的集合，而 $K(j)$ 和 $J'(k)$ 则是与操控二重和式的性质 $P(j,k)$ 相对应的集合。但是存在一些重要的特殊情形，在其中集合 $J$、$K(j)$、$K'$ 与 $J'(k)$ 都有简单的形式。它们频繁出现在应用中。例如，下面是一个特别有用的分解： $$ [1\leqslant j\leqslant n][j\leqslant k\leqslant n]=[1\leqslant j\leqslant k\leqslant n]=[1\leqslant k\leqslant n][1\leqslant j\leqslant k]~.\tag{2.31} $$ 这个艾弗森方程允许我们写成 $$ \sum_{j=1}^n\sum_{k=j}^na_{j,k}=\sum_{1\leqslant j\leqslant k\leqslant n}a_{j,k}=\sum_{k=1}^n\sum_{j=1}^ka_{j,k}~.\tag{2.32} $$ 在这两个和式的和式中，通常一个比另一个更容易计算，我们可以利用 $(2.32)$ 把困难的那个转换到容易的那个。

（现在是做热身题 4 和 6 的最佳时机。）
（抑或也是品尝你所喜爱的士力架美食的大好时机。）

让我们将这些想法应用到一个有用的例子上。考虑由 $n^2$ 个乘积 $a_ja_k$ 组成的阵列 $$ \begin{bmatrix}a_1a_1&a_1a_2&a_1a_3&\cdots&a_1a_n\\[0.5ex]a_2a_1&a_2a_2&a_2a_3&\cdots&a_2a_n\\[0.5ex]a_3a_1&a_3a_2&a_3a_3&\cdots&a_3a_n\\[0.5ex]\vdots&\vdots&\vdots&\ddots&\vdots\\[0.5ex]a_na_1&a_na_2&a_na_3&\cdots&a_na_n\end{bmatrix}. $$ 我们的目的是对 $$ S_◹=\sum_{1\leqslant j\leqslant k\leqslant n}a_ja_k $$ 求一个简单的公式，它是这个阵列的主对角线及其上方的所有元素之和。由于 $a_ja_k=a_ka_j$，故此阵列关于它的主对角线是对称的，从而 $S_◹$ 近似等于所有元素和的一半（除了考虑主对角线时所加的一个修正因子之外）。

rocky road 风味冰激淋里有软糖吗？

这样的考虑启发我们想到如下的处理方法。我们有 $$ S_◹=\sum_{1\leqslant j\leqslant k\leqslant n}a_ja_k=\sum_{1\leqslant k\leqslant j\leqslant n}a_ka_j=\sum_{1\leqslant k\leqslant j\leqslant n}=a_ja_k=S_◺~, $$ 因为我们可以将 $(j,k)$ 更名为 $(k,j)$。此外，由于 $$ [1\leqslant j\leqslant k\leqslant n]+[1\leqslant k\leqslant j\leqslant n]=[1\leqslant j,k\leqslant n]+[1\leqslant j=k\leqslant n]~, $$ 我们就有 $$ 2S_◹=S_◹+S_◺=\sum_{1\leqslant j,k\leqslant n}a_ja_k+\sum_{1\leqslant j=k\leqslant n}a_ja_k~. $$ 根据一般的分配律 $(2.28)$，第一个和式等于 $\big(\hspace{-0.15em}\sum_{j=1}^na_j\big)\hspace{-0.1em}\big(\hspace{-0.15em}\sum_{k=1}^na_k\big)=\big(\hspace{-0.15em}\sum_{k=1}^na_k\big)^2$，而第二个和式是 $\sum_{k=1}^na_k^2$。于是，我们有 $$ S_◹=\sum_{1\leqslant j\leqslant k\leqslant n}a_ja_k=\frac12\hspace{-0.2em}\left(\left(\sum_{k=1}^na_k\right)^2+\sum_{k=1}^na_k^2\right)~,\tag{2.33} $$ 这是用更简单的单个指标和对上三角形和给出的表达式。

受这一成功所鼓舞，我们来研究另外一个二重和式： $$ S=\sum_{1\leqslant j

$$ [1\leqslant j

回到我们中断的地方，现在可以统统除以 $2$ 并重新排序，就得到一个有趣的公式： $$ \left(\sum_{k=1}^na_k\right)\hspace{-0.25em}\left(\sum_{k=1}^nb_k\right)=n\sum_{k=1}^na_kb_k-\sum_{1\leqslant j

（切比雪夫实际上是对积分而不是对和式证明了类似的结果：如果 $f(x)$ 和 $g(x)$ 是单调非减函数，那么 $\left(\int_a^bf(x)\mathrm dx\right)\hspace{-0.25em}\left(\int_a^bg(x)\mathrm dx\right)\leqslant(b-a)\hspace{-0.25em}\left(\int_a^bf(x)g(x)\mathrm dx\right)$。）

这个恒等式得到称为切比雪夫单调不等式（Chebyshev's monotonic inequality）的一个特例： $$ \begin{array}{l}\displaystyle\left(\sum_{k=1}^na_k\right)\hspace{-0.25em}\left(\sum_{k=1}^nb_k\right)\leqslant n\sum_{k=1}^na_kb_k~,\quad a_1\leqslant\cdots\leqslant a_n\text{ 且 }b_1\leqslant\cdots\leqslant b_n~,\\\displaystyle\left(\sum_{k=1}^na_k\right)\hspace{-0.25em}\left(\sum_{k=1}^nb_k\right)\geqslant n\sum_{k=1}^na_kb_k~,\quad a_1\leqslant\cdots\leqslant a_n\text{ 且 }b_1\geqslant\cdots\geqslant b_n~.\end{array} $$ （一般来说，如果 $a_1\leqslant\cdots\leqslant a_n$，且 $p$ 是 ${1,\cdots\,!,n}$ 的一个排列，那么不难证明，当 $b_{p(1)}\leqslant\cdots\leqslant b_{p(n)}$ 时 $\sum_{k=1}^na_kb_{p(k)}$ 的最大值出现，而当 $b_{p(1)}\geqslant\cdots\geqslant b_{p(n)}$ 时它的最小值出现。）

多重求和与单个和式中改变求和指标的一般性运算存在着有趣的联系。由交换律我们知道，如果 $p(k)$ 是这些整数的任意一个排列，则 $$ \sum_{k\in K}a_k=\sum_{p(k)\in K}a_{p(k)}~. $$ 如果 $f$ 是一个任意的函数 $$ f:J\to K~, $$ 它将整数 $j\in J$ 变成整数 $f(j)\in K$，那么用 $f(j)$ 替换 $k$ 会发生什么？指标替换的一般公式是 $$ \def\o{\operatorname}\sum_{j\in J}a_{f(j)}=\sum_{k\in K}a_k\o\#f^-(k)~,\tag{2.35} $$ 这里，$#f^-(k)$ 表示集合 $$ f^-(k)=\big\{j~\big|~f(j)=k\big\} $$ 中的元素个数，即使得 $f(j)$ 等于 $k$ 的 $j\in J$ 的值的个数。

由于 $\sum_{j\in J}[f(j)=k]=\#f^-(k)$，容易通过交换求和次序来证明 $(2.35)$， $$ \sum_{j\in J}a_{f(j)}=\sum_{\substack{j\in J\\[0.5ex]k\in K}}a_k[f(j)=k]=\sum_{k\in K}a_k\sum_{j\in J}[f(j)=k]~. $$ 在 $f$ 是 $J$ 与 $K$ 之间的一一对应这一特殊情形中，对所有的 $k$ 我们都有 $#f^-(k)=1$，而一般公式 $(2.35)$ 就转化为

我的另一位数学老师称它是 “双射”，或许有一天我能逐渐喜欢上这个单词。

$$ \sum_{j\in J}a_{f(j)}=\sum_{f(j)\in K}a_{f(j)}=\sum_{k\in K}a_k~. $$

然后再次……

这就是前面给出的交换律 $(2.17)$，不过稍有变化。

到目前为止，我们的多重和式的例子全都含有 $a_k$ 或者 $b_k$ 这样的通项。但是这本书本应是具体的，所以我们来看一个包含实际数字的多重和式： $$ S_n=\sum_{1\leqslant j

小心，作者似乎认为 $j$、$k$ 和 $n$ 都是 “实际的数”。

例如，$S_1=0$，$S_2=1$，$S_3=\dfrac1{2-1}+\dfrac1{3-1}+\dfrac1{3-2}=\dfrac52$。

计算二重和式的正规方法是首先对 $j$ 或者对 $k$ 求和，让我们来探讨两种选择。 $$ \def\le{\leqslant}\begin{aligned}S_n&=\sum_{1\le k\le n}\sum_{1\le j

摆脱其控制。

如果我们尝试首先用另一种方式求和，就得到 $$ \def\le{\leqslant}\begin{aligned}S_n&=\sum_{1\le j\le n}\sum_{j

但是还有另一种做法，如果在决定要将 $S_n$ 转化成和式的和式之前先用 $k+j$ 替换 $k$： $$ \def\le{\leqslant}\begin{aligned}S_n&=\sum_{1\le j

这里写成 $k\leqslant n$ 而不写成 $k\leqslant n-1$ 是明智之举，简单的界限可以节约劳力。

啊哈！我们求出了 $S_n$。将它与错误的开始结合起来，我们进一步得到了一个恒等式（算是奖赏）： $$ \sum_{0\leqslant k

2.5 一般性的方法 GENERAL METHODS

现在，我们从若干不同的角度研究一个简单的例子，以此巩固所学得的知识。在下面几页中，我们打算对前 $n$ 个正整数的平方和（我们称它为 $\square_n$） $$ \square_n=\sum_{0\leqslant k\leqslant n}k^2~,\quad n\geqslant0\tag{2.37} $$ 求出封闭形式。我们会看到，解决这个问题至少有 8 种不同的方法。在此过程中，我们将会学到解决一般情形下求和问题的有用策略。

像通常一样，我们首先来观察几个小的情形。 $$ \def\arraystretch{1.25}\begin{array}{l|lllllllllllll}n\hspace{1.5em}&0&1&2&3&4&5&6&7&8&9&10&11&12\\\hline n^2&0&1&4&9&16&25&36&49&64&81&100&121&144\\\hline\square_n&0&1&5&14&30&55&91&140&204&285&385&506&650\end{array} $$ 不能很明显地看出 $\square_n$ 的封闭形式，但是当我们确实找到这样一个封闭形式时，可以利用这些值进行检验。

方法 0：查找公式

像求前 $n$ 个的平方和这样的问题可能以前就已解决了，所以从手头的参考资料中很有可能找到它的解。的确如此，在 CRC Standard Mathematical Tables 的第 36 页上就有答案： $$ \square_n=\frac{n(n+1)(2n+1)}6~,\quad n\geqslant0~.\tag{2.38} $$ 只是为了确认没有看错，我们检查这个公式，它正确地给出了 $\square_5=5\times6\times11/6=55$。附带指出，在 CRC Tables 的第 36 页上还有关于立方和、……、十次方和的更多信息。

数学公式的一个权威参考资料是由 Abramowitz 和 Stegun 所编辑的 Handbook of Mathematical Functions。这本书的第 813~814 页列出了 $\square_n$ 对 $n\leqslant100$ 的值，而在第 804 页和第 809 页给出了与 $(2.38)$ 等价的公式，还有关于立方和、……、十五次方和的类似公式（有或者没有交错符号）。

（更困难的和式可以在 Hansen 的包罗万象的表中找到。）

但是，关于序列问题的解答，最好的资料来源是 Sloane 所著的一本名叫 Handbook of Integer Sequences 的小书。它用数值列出了数以千计的序列。如果你碰巧遇到一个怀疑已被研究过的递归式，所要做的就是计算足够多的项，以便将你的递归式与其他著名的递归式区别开来，然后你就有可能在 Sloane 的 Handbook 一书中发现有关文献的指示。例如，$1,5,14,30,\cdots$ 就是一个标号为 1574 的 Sloane 序列，它被称为 “平方金字塔数” 序列（因为在一个用 $n^2$ 个球做正方形地基的金字塔中有 $\square_n$ 个球）。Sloane 给出了 3 个参考文献，其中一个就是我们提到的由 Abramowitz 和 Stegun 编纂的手册。

探索累积了数学智慧的世界宝库的另一个方法是利用计算机程序（例如 Axiom、MACSYMA、Maple 或者 Mathematica），这些程序提供了符号运算的工具。这样的程序是必不可少的，尤其是对需要处理庞大公式的人来说。

熟悉标准的信息源是有益的，因为它们能带来极大的帮助。但是方法 0 与本书的精神并不一致，因为我们希望知道怎样才能由我们自己想出问题的答案。查找的方法仅限于那些其他人已经判决为值得考虑的问题，那里不会有新的问题。

或者，至少是与其他人已经决定要考虑的问题有相同答案的问题。

方法 1：猜测答案，用归纳法证明之

好像是一只小鸟把问题的答案告诉了我们，或者是我们已经用其他某些不太严格的方法得到了一个封闭形式，然后我们只需要证明它是正确的。

例如，我们或许已经注意到了 $\square_n$ 的值有较小的素因子，所以会发现公式 $(2.38)$ 对于较小的 $n$ 值有效。或许我们也猜到更好一些的等价公式 $$ \square_n=\cfrac{n\hspace{-0.2em}\left(n+\cfrac12\right)(n+1)}3,\quad n\geqslant0,\tag{2.39} $$ 因为它更容易记忆。有众多的证据支持 $(2.39)$，但是我们必须排除所有合理的怀疑来证明我们的猜想。数学归纳法就是为此目的而创立的。

“好的，很荣幸，我们知道 $\square_0=0=0\hspace{-0.2em}\left(0+\dfrac12\right)(0+1)/3$，所以基础是很容易验证的。对于归纳步骤，假设 $n>0$，并假设当用 $n-1$ 替换 $n$ 时 $(2.39)$ 成立。由于 $$ \square_n=\square_{n-1}+n^2~, $$ 我们就有 $$ \begin{aligned}3\square_n&=(n-1)\hspace{-0.2em}\left(n-\frac12\right)(n)+3n^2\\&=\left(n^3-\frac32n^2+\frac12n\right)+3n^2\\&=\left(n^3+\frac32n^2+\frac12n\right)\\&=n\hspace{-0.2em}\left(n+\frac12\right)(n+1)~.\end{aligned} $$ 因此 $(2.39)$ 的确对所有 $n\geqslant0$ 都成立，这排除了合理的怀疑。” 法官 Wapner 以他无限的智慧同意这一判断。

归纳法有它的地位，它比试图查找答案更值得推荐，但它仍然不是我们想要寻找的方法。到目前为止，在这一章里计算过的所有其他和式都未用归纳法就得到了解决，我们也希望同样从零开始来确定 $\square_n$ 这样的和式。闪光的灵感并不是必须的，我们希望即便是在缺少创造性思想的日子里也能求解和式。

方法 2：对和式用扰动法

所以，我们来看对几何级数 $(2.25)$ 非常有效的扰动法。我们抽出 $\square_{n+1}$ 的第一项和最后一项，得到 $\square_n$ 的第一个方程： $$ \def\le{\leqslant}\begin{aligned}\square_n+(n+1)^2&=\sum_{0\le k\le n}(k+1)^2=\sum_{0\le k\le n}(k^2+2k+1)\\&=\sum_{0\le k\le n}k^2+2\sum_{0\le k\le n}k+\sum_{0\le k\le n}1\\&=\square_n+2\sum_{0\le k\le n}k+(n+1)~.\end{aligned} $$

噢，上帝！$\square_n$ 相互抵消了。尽管我们竭尽努力，扰动法偶尔也产生了像 $\square_n=\square_n$ 这样的结果，这样我们就失败了。

看起来更像是打平了。

另一方面，这次推导也并非完全失败，它的确揭示了一种方法，把前几个非负整数之和化为封闭形式 $$ 2\sum_{0\leqslant k\leqslant n}k=(n+1)^2-(n+1)~, $$ 尽管我们希望求的是前几个非负整数的平方和。如果从整数的立方和出发，并把它记为 $❒_n$，我们会对整数平方和得到一个表达式吗？我们来试一试。 $$ \begin{aligned}❒_n+(n+1)^3=\sum_{0\leqslant k\leqslant n}(k+1)^3&=\sum_{0\leqslant k\leqslant n}(k^3+3k^2+3k+1)\\&=❒_n+3\square_n+3\frac{(n+1)n}2+(n+1)~.\end{aligned} $$ 足以确信的是，$❒_n$ 被消除了，我们无需依赖归纳法就得到足够的信息以确定 $\square_n$：

方法 2'：扰动了你的助教。

$$ \begin{aligned}3\square_n&=(n+1)^3-3(n+1)n/2-(n+1)\\&=(n+1)\hspace{-0.25em}\left(n^2+2n+1-\frac32n-1\right)=(n+1)\hspace{-0.25em}\left(n+\frac12\right)n~.\end{aligned} $$

方法 3：建立成套方法

把递归式 $(2.7)$ 稍作推广也足以应付包含 $n^2$ 的求和项。递归式 $$ \begin{aligned}R_0&=\alpha~;\\R_n&=R_{n-1}+\beta+\gamma n+\delta n^2~,\quad n>0\end{aligned}\tag{2.40} $$ 的解的一般形式是 $$ R_n=A(n)\alpha+B(n)\beta+C(n)\gamma+D(n)\delta~,\tag{2.41} $$ 因为当 $\delta=0$ 时 $(2.40)$ 与 $(2.7)$ 相同，所以我们就确定了 $A(n)$、$B(n)$ 和 $C(n)$。如果现在把 $R_n=n^3$ 代入，我们发现 $n^3$ 就是当 $\alpha=0$，$\beta=1$，$\gamma=-3$，$\delta=3$ 时的解。从而 $$ 3D(n)-3C(n)+B(n)=n^3~; $$ 这就确定了 $D(n)$。

我们对和式 $\square_n$ 感兴趣，它等于 $\square_{n-1}+n^2$，故而，如果在 $(2.41)$ 中令 $\alpha=\beta=\gamma=0$ 以及 $\delta=1$，我们就得到 $\square_n=R_n$。其次有 $\square_n=D(n)$。我们不需要用代数方法从 $B(n)$ 和 $C(n)$ 计算 $D(n)$，因为我们已经知道答案会是什么，怀疑者应该消除疑虑了，他们会确信 $$ 3D(n)=n^3+3C(n)-B(n)=n^3+3\frac{(n+1)n}2-n=n\hspace{-0.2em}\left(n+\frac12\right)(n+1)~. $$

方法 4：用积分替换和式

学习离散数学的人熟悉 $\Sigma$，而学习微积分的人更熟悉 $\int$，故他们发现将 $\Sigma$ 改变成 $\int$ 是很自然的事。在这本书里，我们的目标之一就是要对 $\Sigma$ 更得心应手地加以处理，从而认为 $\int$ 要比 $\Sigma$ 更困难（至少对精确结果来说是如此）。但是，探索 $\Sigma$ 和 $\int$ 之间的关系仍不失为一个好想法，因为求和与积分基于非常相似的思想。

在微积分中，一个积分可以看成是曲线下面的面积，我们将接触这条曲线的狭长小矩形的面积相加来近似这个面积。也可以用另一种方法，如果给定一组狭长小矩形：由于 $\square_n$ 是大小为 $1\times1,1\times4,\cdots\,\!,1\times n^2$ 矩形的面积之和，所以它近似等于 $0$ 与 $n$ 之间曲线 $f(x)=x^2$ 下面的面积，

（此处省略一张图）

此处的水平单位是垂直单位的 10 倍。

这条曲线下方的面积是 $\int_0^nx^2\mathrm dx=n^3/3$，所以我们知道 $\square_n$ 近似等于 $\dfrac{n^3}3$。

利用这一事实的一个方法是检查这个近似的误差，即 $E_n=\square_n-\dfrac{n^3}3$。由于 $\square_n$ 满足递归式 $\square_n=\square_{n-1}+n^2$，我们发现 $E_n$ 满足更简单的递归式 $$ \begin{aligned}E_n&=\square_n-\frac{n^3}3=\square_{n-1}+n^2-\frac{n^3}3=E_{n-1}+\frac13(n-1)^3+n^2-\frac{n^3}3\\&=E_{n-1}+n-\frac13~.\end{aligned} $$ 另一种寻求此积分近似的方法是通过对楔形误差项的面积求和来得到一个关于 $E_n$ 的公式。我们有 $$ \begin{aligned}\square_n-\int_0^nx^2\mathrm dx&=\sum_{k=1}^n\left(k^2-\int_{k-1}^kx^2\mathrm dx\right)\\&=\sum_{k=1}^n\left(k^2-\frac{k^3-(k-1)^3}3\right)=\sum_{k=1}^n\left(k-\frac13\right).\end{aligned} $$

这是为痴迷微积分的人而写的。

无论哪一种方法都能求得 $E_n$，这样就得到 $\square_n$。

方法 5：展开和收缩

还有另一个方法来发现 $\square_n$ 的封闭形式，它是用一个看起来更为复杂的二重和式替换原来的和式，这个二重和式如果拿捏得当，实际上是可以化简的： $$ \def\le{\leqslant}\begin{aligned}\square_n&=\sum_{1\le k\le n}k^2=\sum_{1\le j\le k\le n}k\\&=\sum_{1\le j\le n}\sum_{j\le k\le n}k\\&=\sum_{1\le j\le n}\left(\frac{j+n}2\right)(n-j+1)\\&=\frac12\sum_{1\le j\le n}\left(n(n+1)+j-j^2\right)\\&=\frac12n^2(n+1)+\frac14n(n+1)-\frac12\square_n=\frac12n\hspace{-0.2em}\left(n+\frac12\right)(n+1)-\frac12\square_n~.\end{aligned} $$

（这里的最后一步有点像扰动法的最后一步，因为我们在两边得到关于未知量的一个方程。）

从单重和式过渡到二重和式，初看似乎是一种倒退，但实际上是进步，因为产生了更容易处理的和式。我们不可能指望不断地简化，简化，再简化来解决每一个问题：你不可能只向上爬坡而登上最高的山峰。

方法 6：用有限微积分

方法 7：用生成函数

当我们学习了下一节及后面各章中更多的技术之后，再继续进行有关 $\square_n=\sum_{k=0}^nk^2$ 的更为激动人心的计算。

2.6 有限微积分和无限微积分 FINITE AND INFINITE CALCULUS

我们已经学习了多种直接处理和式的方法，现在需要用更为广阔的视野，从更高的层次来审视求和问题。数学家们发展出了与更为传统的无限微积分类似的 “有限微积分”，由此有可能用一种更时尚、更系统的方式处理和式。

无限微积分基于由 $$ \mathrm Df(x)=\lim_{h\to0}\frac{f(x+h)-f(x)}h $$ 所定义的**微分**（derivative）算子 $\mathrm D$ 的性质。有限微积分则是基于由 $$ \Delta f(x)=f(x+1)-f(x)\tag{2.42} $$ 所定义的**差分**（difference）算子 $\Delta$ 的性质。差分算子是微分的有限模拟，其中限制了取 $h$ 的正整数值。于是当 $h\to0$ 时，$h=1$ 是我们所能达到的最近的 “极限”，而 $\Delta f(x)$ 则是 $\big(f(x+h)-f(x)\big)/h$ 当 $h=1$ 时的值。

符号 $\mathrm D$ 和 $\Delta$ 称为算子（operator），因为它们作用（operate）在函数上给出新的函数，它们是函数的函数，用于产生函数。如果 $f$ 是从实数到实数的一个适当光滑的函数，那么 $\mathrm Df$ 也是一个从实数到实数的函数。又如果 $f$ 是任意一个从实数到实数的函数，那么 $\Delta f$ 亦然。函数 $\mathrm Df$ 和 $\Delta f$ 在点 $x$ 处的值由上面的定义给出。

与磁带的功能（function）相反。

早先我们在微积分中学习了 $\mathrm D$ 如何作用在幂函数 $f(x)=x^m$ 上。在此情形中，有 $\mathrm Df(x)=mx^{m-1}$。我们可以略去 $f$，将此式非正式地写成 $$ \mathrm D(x^m)=mx^{m-1}~. $$ 如果 $\Delta$ 算子也能产生一个同样优美的结果，那就很好，可惜它不行。例如，我们有 $$ \Delta(x^3)=(x+1)^3-x^3=3x^2+3x+1~. $$ 但是有一类 “$m$ 次幂”，它在 $\Delta$ 的作用下的确可以很好地变换，这就是有限微积分的意义所在。这种新型的 $m$ 次幂由规则

数学强人（power）。

$$ x^{\underline m}=\overbrace{x(x-1)\cdots(x-m+1)}^{m\text{个因子}}~,\quad\text{整数 }m\geqslant0\tag{2.43} $$ 来定义。注意 $m$ 的下方有一条小直线，它表示这 $m$ 个因子是阶梯般地一直向下再向下。还有一个对应的定义，其中的因子一直向上再向上： $$ x^{\overline m}=\overbrace{x(x+1)\cdots(x+m-1)}^{m\text{个因子}}~,\quad\text{整数 }m\geqslant0~.\tag{2.44} $$ 当 $m=0$ 时，我们有 $x^{\underline0}=x^{\overline0}=1$，因为通常一个没有任何因子的乘积取值为 $1$（恰与不含任何项的和式通常取值为 $0$ 一样）。

如果要大声读出量 $x^{\underline m}$，它称为 “$x$ 直降 $m$ 次”；类似地，$x^{\overline m}$ 就是 “$x$ 直升 $m$ 次”。这些函数也称为下降阶乘幂（falling factorial power）和上升阶乘幂（rising factorial power），因为它们与阶乘函数 $n!=n(n-1)\cdots(1)$ 密切相关。事实上，我们有 $n!=n^{\underline n}=1^{\overline n}$。

有关阶乘幂的其他若干记号也出现在数学文献中，特别是对于 $x^{\overline m}$ 或者 $x^{\underline m}$ 的 “Pochhammer 符号” $(x)_m$，像 $x^{(m)}$ 或者 $x_{(m)}$ 这样的记号也被看成是 $x^{\underline m}$。但是这种下划线和上划线用法很流行，因为它容易书写，容易记忆，且不需要多余的括号。

数学术语有时难以捉摸：Pochhammer 实际上是对二项式系数 $\dbinom xm$ 而不是对阶乘幂用到了记号 $(x)_m$。

下降的幂 $x^{\underline m}$ 对 $\Delta$ 特别适合。我们有 $$ \begin{aligned}\Delta(x^{\underline m})&=(x+1)^{\underline m}-x^{\underline m}\\&=(x+1)x\cdots(x-m+2)-x\cdots(x-m+2)(x-m+1)\\&=mx(x-1)\cdots(x-m+2)~,\end{aligned} $$ 因此，有限微积分有现成的规则可与 $\mathrm D(x^m)=mx^{m-1}$ 媲美： $$ \Delta(x^{\underline m})=mx^{\underline{m-1}}~.\tag{2.45} $$ 这就是基本的阶乘结果。

无限微积分的算子 $\mathrm D$ 有一个逆运算，即逆微分算子（或积分算子）$\int$。微积分基本定理把 $\mathrm D$ 和 $\int$ 联系起来： $$ g(x)=\mathrm Df(x)\text{ 当且仅当 }\int g(x)\mathrm dx=f(x)+C~. $$ 这里 $\int g(x)\mathrm dx$ 是 $g(x)$ 的不定积分，它是导数等于 $g(x)$ 的一个函数类。类似地，$\Delta$ 也有一个逆运算，即逆差分算子（或求和算子）$\Sigma$，而且有一个类似的基本定理： $$ g(x)=\Delta f(x)\text{ 当且仅当 }\sum g(x)\delta x=f(x)+C~.\tag{2.46} $$

“正如我们用符号 $\Delta$ 来表示差分那样，我们将用符号 $\Sigma$ 来表示和。……由此得到等式 $z=\Delta y$，如果逆转过来，也就得到 $y=\sum z+C$。” ——欧拉

这里 $\sum g(x)\delta x$ 是 $g(x)$ 的不定和式（indefinite sum），是差分等于 $g(x)$ 的一个函数类（注意，小写 $\delta$ 和大写 $\Delta$ 相关，就像 $d$ 与 $D$ 有关一样）。不定积分中的 $C$ 是一个任意常数，而不定和中的 $C$ 则是满足 $p(x+1)=p(x)$ 的任意一个函数 $p(x)$。例如，$C$ 可以是周期函数，$a+b\sin2\pi x$，当我们取差分时，这样的函数会被消去，正如在求导数时常数会被消去一样。在 $x$ 的整数值处，函数 $C$ 是常数。

现在我们可以讨论关键点了。无限微积分也有定（definite）积分：如果 $g(x)=\mathrm Df(x)$，那么 $$ \int_a^bg(x)\mathrm dx=f(x)\big|_a^b=f(b)-f(a)~. $$ 于是，有限微积分——一直在模仿其更出名的同类——也有确定的**和式**（sum）：如果 $g(x)=\Delta f(x)$，那么 $$ \sum\nolimits_a^bg(x)\delta x=f(x)\big|_a^b=f(b)-f(a)~.\tag{2.47} $$ 这个公式让记号 $\sum_a^bg(x)\delta x$ 有了意义，恰如上面的公式定义了 $\int_a^bg(x)\mathrm dx$。

但是直观上讲，$\sum_a^bg(x)\delta x$ 的真正含义是什么？我们是用类比的方法定义了它，但并不必要。我们想保持相似性，以便更容易记住有限微积分的法则，但是如果我们不理解它的意义，那么这记号就没有用处。让我们首先观察某些特殊情形来导出它的意义，假设 $g(x)=\Delta f(x)=f(x+1)-f(x)$。如果 $b=a$，我们就有 $$ \sum\nolimits_a^ag(x)\delta x=f(a)-f(a)=0~. $$ 其次，如果 $b=a+1$，结果就是 $$ \sum\nolimits_a^{a+1}g(x)\delta x=f(a+1)-f(a)=g(a)~. $$ 更一般地，如果 $b$ 增加 $1$，我们就有 $$ \begin{aligned}\sum\nolimits_a^{b+1}g(x)\delta x-\sum\nolimits_a^bg(x)\delta x&=\big(f(b+1)-f(a)\big)-\big(f(b)-f(a)\big)\\&=f(b+1)-f(b)=g(b)~.\end{aligned} $$ 根据这些观察和数学归纳法，我们推出，当 $a$ 和 $b$ 是整数且 $b\geqslant a$ 时，$\sum_a^bg(x)\delta x$ 一般的确切含义是： $$ \sum\nolimits_a^bg(x)\delta x=\sum_{k=a}^{b-1}g(k)=\sum_{a\leqslant k

这算画龙点睛吗？

我们尝试用稍微不同的方式重新简要地对此加以叙述。假设给定一个未知的和式，希望用封闭形式对它的值进行计算，并假设可以将它写成形式 $\sum_{a\leqslant k叠缩（telescoping），与一台折叠的望远镜类似，因为一台折叠的望远镜的厚度仅仅由最外面的镜筒的外半径和最里面的镜筒的内半径来决定。】

我始终认为它是叠缩，因为它从一个很长的表达式收缩成一个很短的表达式。

但是法则 $(2.48)$ 仅当 $b\geqslant a$ 时才适用，如果 $b

现在，其他人要对此疑惑一段时间了。

$$ \sum_{0\leqslant k

特别地，当 $m=1$ 时我们有 $k^{\underline1}=k$，所以借助有限微积分的原理，我们很容易地记住 $$ \sum_{0\leqslant k

通常的幂也可以用这样的新方法来求和，如果我们首先用下降幂将它们表示出来。例如， $$ k^2=k^{\underline2}+k^{\underline1}~, $$ 所以 $$ \sum_{0\leqslant k

与这样的朋友……

天哪，这太容易了。事实上，这比在前一节里斩获这一公式的诸多其他方法中的任何一种都更容易。所以让我们再上一个层次，从平方到立方（cube）：简单的计算表明 $$ k^3=k^{\underline3}+3k^{\underline2}+k^{\underline1}~. $$ （利用我们将在第 6 章里研究的斯特林数，总能在通常的幂和阶乘幂之间进行转换。）从而 $$ \sum_{a\leqslant k

到目前为止，我们仅仅考虑了非负指数的下降幂。为了将这个与通常幂类似的对象推广到负指数的情形，我们需要在 $m<0$ 时给出 $x^{\underline m}$ 的恰当定义。观察序列 $$ \begin{aligned}x^{\underline3}&=x(x-1)(x-2)~,\\x^{\underline2}&=x(x-1)~,\\x^{\underline1}&=x~,\\x^{\underline0}&=1~,\end{aligned} $$ 我们注意到，用 $x-2$ 来除，从 $x^{\underline3}$ 得到 $x^{\underline2}$；然后再用 $x-1$ 来除，从 $x^{\underline2}$ 得到 $x^{\underline1}$；最后再用 $x$ 来除，从 $x^{\underline1}$ 得到 $x^{\underline0}$。看起来，接下来用 $x+1$ 来除，从 $x^{\underline0}$ 得到 $x^{\underline{-1}}$ 是合理的，这样就得到 $x^{\underline{-1}}=1/(x+1)$。继续下去，前面几个负指数的下降幂是 $$ \begin{aligned}x^{\underline{-1}}&=\frac1{x+1}~,\\x^{\underline{-2}}&=\frac1{(x+1)(x+2)}~,\\x^{\underline{-3}}&=\frac1{(x+1)(x+2)(x+3)}~,\end{aligned} $$ 对于负指数的下降幂的一般定义是 $$ x^{\underline{-m}}=\frac1{(x+1)(x+2)\cdots(x+m)}~,\quad m>0~.\tag{2.51} $$ （也能对实数甚至复数 $m$ 来定义下降幂，但是我们将此事推迟到第 5 章。）

复数怎么能是偶数呢？

正文中 “甚至复数” 的英语表述是 even complex，作者在这里利用 even 的另一数学含义 “偶数” 故意将正文中的 even complex 说成是 “偶的复数” 以制造诙谐打趣气氛。

法则有它们的拥护者和诋毁者。

现在让我们来确认，对我们新近定义的下降幂，关键性的差分性质成立。当 $m<0$ 时是否有 $\Delta x^{\underline m}=mx^{\underline{m-1}}$？例如，如果 $m=-2$，其差分是 $$ \begin{aligned}\Delta x^{\underline{-2}}&=\frac1{(x+2)(x+3)}-\frac1{(x+1)(x+2)}\\&=\frac{(x+1)-(x+3)}{(x+1)(x+2)(x+3)}\\&=-2x^{\underline{-3}}~.\end{aligned} $$ 是的，它成立！类似的讨论对所有 $m<0$ 也适用。

这样一来，求和性质 $(2.50)$ 不但对正的下降幂成立，对负的下降幂也成立，只要不出现用零做除数的情形： $$ \sum\nolimits_a^bx^{\underline m}\delta x=\frac{x^{\underline{m+1}}}{m+1}\Bigg|_a^b~,\quad m\ne-1~. $$ 但是当 $m=-1$ 时又如何呢？回想一下对积分的情形，当 $m=-1$ 时我们有 $$ \int_a^bx^{-1}\mathrm dx=\ln x\big|_a^b~. $$ 我们希望 $\ln x$ 有一个有限模拟，换句话说，我们要寻求一个函数 $f(x)$，使得 $$ x^{\underline{-1}}=\frac1{x+1}=\Delta f(x)=f(x+1)-f(x)~. $$ 不难看出，当 $x$ 是整数时， $$ f(x)=\frac11+\frac12+\cdots+\frac1x $$ 就是这样一个函数，而这个量恰好就是 $(2.13)$ 中的调和数 $H_x$。于是 $H_x$ 就是连续的 $\ln x$ 的离散模拟。（第 6 章将对非整数的 $x$ 定义 $H_x$，不过整数值对于现在的目的来说已经足够用了。在第 9 章里我们还将看到，对于很大的 $x$，$H_x-\ln x$ 的值近似等于 $0.577+1/(2x)$。从而 $H_x$ 与 $\ln x$ 不但类似，它们的值也通常相差小于 $1$。）

正好是 $0.577$ 吗？或许它们指的是 $1/\sqrt3$。然而也有可能并非如此。

现在我们能对下降幂的和式给出完整的描述了： $$ \sum\nolimits_a^bx^{\underline m}\delta x=\left\{\begin{array}{cl}\dfrac{x^{\underline{m+1}}}{m+1}\Bigg|_a^b~,&m\ne-1~,\\[1ex]H_x\big|_a^b~,&m=-1~.\end{array}\right.\tag{2.53} $$ 这个公式指出了，为什么在快速排序这样的离散问题的解中常会冒出调和数，这恰如在连续性问题的解中自然会出现所谓的自然对数一样。

既然我们找到了 $\ln x$ 的一个类似物，我们也来研究下是否有一个 $\mathrm e^x$ 的类似物存在。什么样的函数 $f(x)$ 有与恒等式 $\mathrm{De}^x=\mathrm e^x$ 对应的性质 $\Delta f(x)=f(x)$？这很容易： $$ f(x+1)-f(x)=f(x)\iff 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\ne1$，$c^x$ 的逆差分是 $c^x/(c-1)$。这一事实与基本法则 $(2.47)$ 以及 $(2.48)$ 合起来，就给出了理解几何级数和的一般公式的满意方法： $$ \sum_{a\leqslant k

然而，$\Delta\big(f(x)g(x)\big)$ 的确有比较好的形式，而且提供了一个分部求和（summation by parts）的法则，它是无限微积分中称为分部积分法则的一个有限相似结果。我们回顾一下无限微积分中的公式 $$ \mathrm D(uv)=u\mathrm Dv+v\mathrm Du $$ 在积分并重新排列各项的次序之后，它引导出分部积分法 $$ \int u\mathrm Dv=uv-\int v\mathrm Du~, $$ 我们可以在有限微积分中做类似的事情。

我们先将差分算子运用到两个函数 $u(x)$ 和 $v(x)$ 的乘积： $$ \begin{align}\Delta\big(u(x)v(x)\big)&=u(x+1)v(x+1)-u(x)v(x)\notag\\&=u(x+1)v(x+1)-u(x)v(x+1)\notag\\&\phantom{=u(x+1)v(x+1)-}+u(x)v(x+1)-u(x)v(x)\notag\\&=u(x)\Delta v(x)+v(x+1)\Delta u(x)~.\tag{2.54}\end{align} $$ 这个公式可以利用由 $$ \mathrm Ef(x)=f(x+1) $$ 所定义的**移位算子**（shift operator）$\mathrm E$ 表示成方便的形式。用 $\mathrm Ev(x)$ 替换 $v(x+1)$ 就得到乘积的差分的一个紧凑法则： $$ \Delta(uv)=u\Delta v+\mathrm Ev\Delta u\tag{2.55} $$ （$\mathrm E$ 有一点儿麻烦，但是它使得这个方程变得正确。）在这个方程的两边取不定和，并重新排列它的项，就得到广为宣扬的分部求和法则：

无限微积分在此是通过令 $1\to0$ 避开了 $\mathrm E$。

$$ \sum u\Delta v=uv-\sum\mathrm Ev\Delta u~.\tag{2.56} $$ 如同对于无限微积分那样，可以在所有三项上加上界限，从而使得不定和式变成确定和式。

当左边的和式比右边的和式更难以处理时，这个法则是有用的。我们来看一个例子。函数 $\int x\mathrm e^x\mathrm dx$ 是分部积分的一个典型例子，它的离散模拟是 $\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 Ev(x)=2^{x+1}$。代入 $(2.56)$ 就给出

我猜，对于 $x$ 的很小的值有 $\mathrm e^x=2^x$。

$$ \sum x2^x\delta x=x2^x-\sum2^{x+1}\delta x=x2^x-2^{x+1}+C~. $$ 加上界限，我们可以用此式来计算以前做过的和式： $$ \begin{aligned}\sum_{k=0}^nk2^k&=\sum\nolimits_0^{n+1}x2^x\delta x\\&=x2^x-2^{x+1}\Big|_0^{n+1}\\&=\big((n+1)2^{n+1}-2^{n+2}\big)-(0\times2^0-2^1)=(n-1)2^{n+1}+2~.\end{aligned} $$ 用这个方法比用扰动法更容易求出这个和，因为我们不需要思考。

数学的终极目标是不需要聪明的想法。

在这一章前面，我们碰巧发现了 $\sum_{0\leqslant k

2.7 无限和式 INFINITE SUMS

在这一章开始定义记号 $\Sigma$ 时，我们对无限和问题略施巧计，说本质上 “要等到以后。而现在，我们可以假定遇到的所有和式都只有有限多个非零的项”。但是，考虑的时刻最终还是来了，我们必须面对和式可能是无限的这样一个事实。而实际情况则是，无限和式既带来了好消息，也带来了坏消息。

这是略施巧计？

首先是坏消息：事实已经表明，当涉及无限和式的时候，处理 $\Sigma$ 时所用的方法并不总是有效的。接下来则是好消息：存在一大类容易理解的无限和式，我们对它们做过的所有运算都是完全合法的。在我们更密切审视求和的基本意义之后，这两个消息背后所隐藏的理由将会变得清晰起来。

每个人都知道有限和式指的是什么：一项一项相加，直到把它们全都加在一起。无限和式需要更加仔细地定义，以免陷入荒谬的境地。

例如，很自然可以这样定义，从而使得无限和式 $$ S=1+\frac12+\frac14+\frac18+\frac1{16}+\frac1{32}+\cdots $$ 等于 $2$，因为如果将它加倍就得到 $$ 2S=2+1+\frac12+\frac14+\frac18+\frac1{16}+\cdots=2+S~. $$ 另一方面，同样的推理提示我们应该定义 $$ T=1+2+4+8+16+32+\cdots $$ 是 $-1$，因为如果对它加倍就得到 $$ 2T=2+4+8+16+32+64+\cdots=T-1~. $$

的确：在字的大小是无限的二进制计算机上，$1+2+4+8+\cdots$ 是数 $-1$ 的 “无限精确” 表示。

真是滑稽，正的数值加起来怎么会得到一个负数呢？看来最好不对 $T$ 加以定义，或者似乎应该说成 $T=\infty$，因为 $T$ 中相加的项会大于任何指定的有限数。（注意，$\infty$ 是方程 $2T=T-1$ 的另一个解，也 “解决” 了方程 $2S=2+S$。）

我们尝试对一般和式 $\sum_{k\in K}a_k$ 的值构想一个好的定义，其中 $K$ 可以是无限的。首先，让我们假设所有的项 $a_k$ 都是非负的（nonnegative），这样就不难找到一个合适的定义：如果有一个常数 $A$ 为界，使得对所有有限（finite）子集 $F\subset K$ 都有 $$ \sum_{k\in F}a_k\leqslant A~, $$ 那么我们就定义 $\sum_{k\in K}a_k$ 是**最小的**这样的 $A$。（它由实数众所周知的性质得出：所有这样的 $A$ 总包含一个最小的元素。）如果没有常数 $A$ 为界，我们就说 $\sum_{k\in K}a_k=\infty$，这就意味着，对任何实数 $A$，都有有限多项 $a_k$ 组成的一个集合，它们和超过 $A$。

我们已经详细阐述了上一段中的定义，它与指标集 $K$ 中可能存在的任何次序无关。这样一来，我们打算要讨论适用于带有多个指标 $k_1,k_2,\cdots$ 的多重和式，而不仅仅是指标集为（单一）整数集合的和式。

集合 $K$ 甚至可以是不可数的。但是，如果存在一个常数 $A$ 为界，则仅有可数多项不为零，因为至多有 $nA$ 项 $\geqslant1/n$。

在 $K$ 是非负整数集合的特殊情形下，我们对于非负项 $a_k$ 的定义就意味着 $$ \sum_{k\geqslant0}a_k=\lim_{n\to\infty}\sum_{k=0}^na_k~. $$ 理由是：实数的任何一个非减序列都有极限（可能是 $\infty$）。如果极限是 $A$，又如果 $F$ 是任意一个非负整数的有限集合，其元素全部 $\leqslant n$，我们就有 $\sum_{k\in F}a_k\leqslant\sum_{k=0}^na_k\leqslant A$，因此 $A=\infty$ 或者 $A$ 是一个有界常数。又如果 $A'$ 是任何一个小于所述极限 $A$ 的数，那么就存在一个 $n$，使得 $\sum_{k=0}^na_k>A'$，该有限集 $F={0,1,\cdots\,!,n}$ 证明 $A'$ 不是有界常数。

按照刚刚给出的定义，我们可以很容易地计算某种无限和式的值。例如，如果 $a_k=x^k$，我们就有 $$ \sum_{k\geqslant0}x^k=\lim_{n\to\infty}\frac{1-x^{n+1}}{1-x}=\begin{cases}1/(1-x)~,&0\leqslant x<1~;\\[1ex]\infty~,&x\geqslant1~.\end{cases} $$ 特别地，刚刚考虑过的无限和 $S$ 和 $T$ 分别取值 $2$ 和 $\infty$，恰如我们所猜测的。另一个有趣的例子是 $$ \begin{aligned}\sum_{k\geqslant0}\frac1{(k+1)(k+2)}&=\sum_{k\geqslant0}k^{\underline{-2}}\\&=\lim_{n\to\infty}\sum_{k=0}^{n-1}k^{\underline{-2}}=\lim_{n\to\infty}\frac{k^{\underline{-1}}}{-1}\Bigg|_0^n=1~.\end{aligned} $$ 现在，我们考虑和式中既可能有非负项又可能有负项的情形。例如，

“和式 $a-a+a-a+a-a+\cdots$ 时而 $=a$，时而 $=0$，于是此无穷级数继续下去，可以猜测其和 $=a/2$，我必须承认你的观察力敏锐而准确。“ ——G. Grandi

$$ \sum_{k\geqslant0}(-1)^k=1-1+1-1+1-1+\cdots $$ 的值应该是什么？如果将它成对分组，我们得到 $$ (1-1)+(1-1)+(1-1)+\cdots=0+0+0+\cdots, $$ 所以这个和为零。但是，如果延迟一项再成对分组，我们得到 $$ 1-(1-1)-(1-1)-(1-1)-\cdots=1-0-0-0-\cdots, $$ 这个和是 $1$。

我们或许也可以尝试在公式 $\sum_{k\geqslant0}x^k=1/(1-x)$ 中令 $x=-1$，因为我们已经证明了这个公式当 $0\leqslant x<1$ 时成立，但这样就迫使我们得出结论：这个无限和是 $\dfrac12$，尽管它是由整数组成的和式！

另一个有趣的例子是双向无限的 $\sum_ka_k$，其中当 $k\geqslant0$ 时 $a_k=1/(k+1)$，而当 $k<0$ 时 $a_k=1/(k-1)$。我们可以把它写成 $$ \cdots+\left(-\frac14\right)+\left(-\frac13\right)+\left(-\frac12\right)+1+\frac12+\frac13+\frac14+\cdots~.\tag{2.58} $$ 如果我们从位于 “中心” 的元素开始往外计算这个和式， $$ \cdots+\left(-\frac14\left(-\frac13+\left(-\frac12+(1)+\frac12\right)+\frac13\right)+\frac14\right)+\cdots, $$ 就得到它的值为 $1$；如果我们将所有的括号都向左移一步， $$ \cdots+\left(-\frac15+\left(-\frac14+\left(-\frac13+\left(-\frac12\right)+1\right)+\frac12\right)+\frac13\right)+\cdots, $$ 同样得到值 $1$，因为在最内层的 $n$ 个括号中，所有数之和是 $$ -\frac1{n+1}-\frac1n-\cdots-\frac12+1+\frac12+\cdots+\frac1{n-1}=1-\frac1n-\frac1{n+1}~. $$ 类似的讨论表明，如果将这些括号向左或者向右任意移动固定步，它的值都是 $1$，这使我们有勇气相信这个和式的确是 $1$。另一方面，如果我们以下述方式对项分组 $$ \cdots+\left(-\frac14+\left(-\frac13+\left(-\frac12+1+\frac12\right)+\frac13+\frac14\right)+\frac15+\frac16\right)+\cdots, $$ 那么从内往外的第 $n$ 对括号包含数 $$ -\frac1{n+1}-\frac1n-\cdots-\frac12+1+\frac12+\cdots+\frac1{2n-1}+\frac1{2n}=1+H_{2n}-H_{n+1}~. $$ 在第 9 章里，我们将证明 $\lim_{n\to\infty}(H_{2n}-H_{n+1})=\ln2$，于是这一组合方式表明，这个双向无限和式实际上应该等于 $1+\ln2$。

按照不同方式对其项相加而得出不同值的和式，有某些不同寻常之处。关于分析学的高等教材中有五花八门的定义，它们对这样自相矛盾的和式赋予了有意义的值，但是，如果我们采用那些定义，就不能像一直在做的那样自由地对记号 $\Sigma$ 进行操作。就本书的目的而言，不需要 “条件收敛” 这种精巧的改进，因此我们会坚持使用无限和的一种定义，以保证在这一章里所做的所有运算都是正确的。

事实上，我们关于无限和式的定义相当简单。设 $K$ 是任意一个集合，而 $a_k$ 是对每一个 $k\in K$ 定义的实值项（这里 “$k$” 实际上可以代表若干个指标 $k_1,k_2,\cdots$，因而 $K$ 可以是多维的）。任何实数 $x$ 都可以写成其正的部分减去负的部分 $$ x=x^+-x^-~,\quad\text{其中 }x^+=x\times[x>0]~,\quad x^-=-x\times[x<0]~. $$ （或者 $x^+=0$，或者 $x^-=0$，或者两者皆成立。）我们已经说明了怎样来定义无限和式 $\sum_{k\in K}a_k^+$ 和 $\sum_{k\in K}a_k^-$ 的值，因为 $a_k^+$ 和 $a_k^-$ 都是非负的。这样一来，我们的一般性定义是 $$ \sum_{k\in K}a_k=\sum_{k\in K}a_k^+-\sum_{k\in K}a_k^-~,\tag{2.59} $$ 除非右边的两个和式都等于 $\infty$。在后面这种情形，我们不定义 $\sum_{k\in K}a_k$。

设 $A^+=\sum_{k\in K}a_k^+$，$A^-=\sum_{k\in K}a_k^-$。如果 $A^+$ 和 $A^-$ 两者都是有限的，就说和式 $\sum_{k\in K}a_k$ 绝对收敛（converge absolutely）于值 $A=A^+-A^-$。如果 $A^+=\infty$ 而 $A^-$ 是有限的，就说和式 $\sum_{k\in K}a_k$ 发散（diverge）于 $+\infty$。类似地，如果 $A^-=\infty$ 而 $A^+$ 是有限的，就说 $\sum_{k\in K}a_k$ 发散于 $-\infty$。如果 $A^+=A^-=\infty$，结果还很难说。

换句话说，绝对收敛就意味着绝对值的和式收敛。

我们从对非负项所做的定义开始，然后再将它推广到实值的项。如果项 $a_k$ 是复数，我们可以再次用显然的方式将定义推广：和式 $\sum_{k\in K}a_k$ 定义成 $\sum_{k\in K}\Re a_k+i\sum_{k\in K}\Im a_k$，其中 $\Re a_k$ 和 $\Im a_k$ 是 $a_k$ 的实部和虚部——这两个和式都有定义。反之，没有定义（见习题 18）。

如前所述，坏消息是某些无限和式必须不予定义，因为我们所做的操作在所有这样的情形中都可能产生矛盾（见习题 34）。好消息是，只要我们处理的是刚才所定义的绝对收敛的和式，这一章里的所有操作都完全成立。

通过证明另一个变换法则都保持所有绝对收敛的和式之值不变，我们可以验证好消息。说得更具体一些，这就意味着我们必须证明分配律、结合律以及交换律，加上首先对某一个指标变量求和的法则，还要证明由这四种和式的基本运算所推导出来的每一个结论。

分配律 $(2.15)$ 可以更加精确地表述为：如果 $\sum_{k\in K}a_k$ 绝对收敛于 $A$，且 $c$ 是任意一个复数，那么 $\sum_{k\in K}ca_k$ 绝对收敛于 $cA$。我们可以像上面那样，将和式分成实部和虚部，正的部分和负的部分，再通过证明 $c>0$ 且每一项 $a_k$ 都是非负的这一特殊情形来证明此结论。这一特殊情形的证明得以成功，是因为对所有有限集合 $F$ 都有 $\sum_{k\in F}ca_k=c\sum_{k\in F}a_k$。后面这一事实可以通过对 $F$ 的大小用归纳法得出。

结合律 $(2.16)$ 可以陈述为：如果 $\sum_{k\in K}a_k$ 和 $\sum_{k\in K}b_k$ 绝对收敛于 $A$ 和 $B$，那么 $\sum_{k\in K}(a_k+b_k)$ 绝对收敛于 $A+B$。事实上，这是我们很快就要证明的更加一般的定理的一个特例。

交换律 $(2.17)$ 实际上并不需要证明，因为我们在紧随 $(2.35)$ 的讨论中就已经指出，如何将它作为交换求和次序的一般法则的一个特例推导出来。

在你第一次看到这儿时，最好是先略过这一页。——友好的助教

我们需要证明的主要结果是多重和式的基本原理：经过两个或者多个指标集的绝对收敛的和式永远可以对这些指标中的任何一个首先求和。我们将来会正式地证明：如果 $J$ 是任意的指标集，并且 $\big\{K_j~\big|~j\in J\big\}$ 的元素是任意的指标集，使得 $$ \sum_{\substack{j\in J\\[0.5ex]k\in K_j}}a_{j,k}\text{ 绝对收敛于 }A~, $$ 那么对每一个 $j\in J$ 都存在复数 $A_j$，使得 $$ \begin{aligned}&\sum_{k\in K_j}a_{j,k}\text{ 绝对收敛于 }A_j~,\text{ 且}\\&\sum_{j\in J}A_j\text{ 绝对收敛于 }A~.\end{aligned} $$ 只要在所有的项都为非负时证明这一结论就够了，因为我们可以如前一样，把每一项分解成实部和虚部，正的部分和负的部分来证明一般的情形。于是，我们假设对所有的指标对 $(j,k)\in M$ 都有 $a_{j,k}\geqslant0$，其中 $M$ 是主指标集 $\big{(j,k)~\big|~j\in J,k\in K_j\big}$。

给定 $\sum_{(j,k)\in M}a_{j,k}$ 是有限的，即对所有有限子集 $F\subseteq M$ 有 $$ \sum_{(j,k)\in F}a_{j,k}\leqslant A~, $$ 而 $A$ 是这样的最小上界。如果 $j$ 是 $J$ 的任意一个元素，形如 $\sum_{k\in F_j}a_{j,k}$ 的每一个和都以 $A$ 为上界，其中 $F_j$ 是 $K_j$ 的一个有限子集。从而这些有限和式有一个最小的上界 $A_j\geqslant0$，且根据定义有 $\sum_{k\in K_j}a_{j,k}=A_j$。

我们仍然需要证明：对所有有限子集 $G\subseteq J$，$A$ 是 $\sum_{j\in G}A_j$ 的最小上界。假设 $G$ 是 $J$ 的满足 $\sum_{j\in G}A_j=A'>A$ 的有限子集。我们可以求出一个有限子集 $F_j\subseteq K_j$，使得对每个满足 $A_j>0$ 的 $j\in G$ 均有 $\sum_{k\in F_j}a_{j,k}>(A/A')A_j$。至少存在一个这样的 $j$。但是此时有 $\sum_{j\in G,k\in F_j}a_{j,k}>(A/A')\sum_{j\in G}A_j=A$，这与如下事实矛盾：对所有有限子集 $F\subseteq M$ 有 $\sum_{(j,k)\in F}a_{j,k}\leqslant A$。从而对所有有限子集 $G\subseteq J$ 都有 $\sum_{j\in G}A_j\leqslant A$。

最后，设 $A'$ 是小于 $A$ 的任何一个实数。如果我们能找到一个有限集合 $G\subseteq J$，使得 $\sum_{j\in G}A_j>A'$，证明就完成了。我们知道存在一个有限集合 $F\subseteq M$，使得 $\sum_{(j,k)\in F}a_{j,k}>A'$，设 $G$ 是这个 $F$ 中那些 $j$ 组成的集合，又设 $F_j=\big\{k~\big|~(j,k)\in F\big\}$，那么就有 $\sum_{j\in G}A_j\geqslant\sum_{j\in G}\sum_{k\in F_j}a_{j,k}=\sum_{(j,k)\in F}a_{j,k}>A'$。证明完毕。

好的，现在合法了！我们对无限和式所做的一切都得到了证实，只要它的项的绝对值组成的所有有限和式都有一个有限的界。由于双向无限和式 $(2.58)$ 在我们用两种不同的方法计算时给出两个不同的答案，因而它的正项 $1+\dfrac12+\dfrac13+\cdots$ 必定发散于 $\infty$；否则，不论我们如何对它的项进行分组都会得到同一个答案。

所以为什么我后来会一直听到许多有关 ”调和收敛“ 之类的说法？

习题

热身题

记号 $\sum\limits_{k=4}^0q_k$ 的含义是什么？

化简表达式 $x\times\big([x>0]-[x<0]\big)$。

将和式
$$ \sum_{0\leqslant k\leqslant5}a_k\text{ 与 }\sum_{0\leqslant k^2\leqslant5}a_{k^2} $$ 完全写开以证实你对记号 $\Sigma$ 的理解（注意，第二个和式有一点棘手）。

将三重和式 $$ \sum_{1\leqslant i

下面的推导何处有错？ $$ \left(\sum_{j=1}^na_j\right)\hspace{-0.25em}\left(\sum_{k=1}^n\frac1{a_k}\right)=\sum_{j=1}^n\sum_{k=1}^n\frac{a_j}{a_k}=\sum_{k=1}^n\sum_{k=1}^n\frac{a_k}{a_k}=\sum_{k=1}^nn=n^2~. $$

作为 $j$ 和 $n$ 的函数，$\sum_k[1\leqslant j\leqslant k\leqslant n]$ 的值是什么？

设 $\nabla f(x)=f(x)-f(x-1)$。$\nabla(x^{\overline m})$ 是什么？

当 $m$ 是给定的整数时，$0^{\underline m}$ 的值是什么？

对于上升阶乘幂，与 $(2.52)$ 类似的指数法则是什么？用它来定义 $x^{\overline{-n}}$。

让位给上升的权力。

在英语里，”幂“ 和 ”权力“ 是同一个单词 power。

正文对乘积的差分导出了如下的公式： $$ \Delta(uv)=u\Delta v+\mathrm Ev\Delta u~. $$ 它的左边关于 $u$ 和 $v$ 对称，但其右边不对称，这个公式怎么可能是正确的呢？

基础题

分部求和的一般法则 $(2.56)$ 等价于 $$ \sum_{0\leqslant k

证明：只要 $c$ 是一个整数，函数 $p(k)=k+(-1)^kc$ 就是所有整数集合的一个排列。

利用成套方法求 $\sum_{k=0}^n(-1)^kk^2$ 的封闭形式。

将 $\sum_{k=1}^nk2^k$ 重新改写成多重和式 $\sum_{1\leqslant j\leqslant k\leqslant n}2^k$ 的形式来对它进行计算。

用正文中的方法 5 来计算 $❒_n=\sum_{k=1}^nk^3$：首先记 $❒_n+\square_n=2\sum_{1\leqslant j\leqslant k\leqslant n}jk$，然后应用 $(2.33)$。

证明 $x^{\underline m}/(x-n)^{\underline m}=x^{\underline n}/(x-m)^{\underline n}$，除非其中有一个分母为零。

证明，对于所有的整数 $m$，下面的公式可以用来在上升阶乘幂与下降阶乘幂之间进行转换： $$ \begin{aligned}x^{\overline m}&=(-1)^m(-x)^{\underline m}=(x+m-1)^{\underline m}=1/(x-1)^{\underline{-m}}~;\\x^{\underline m}&=(-1)^m(-x)^{\overline m}=(x-m+1)^{\overline m}=1/(x+1)^{\overline{-m}}~.\end{aligned} $$ （习题 9 的答案给出了 $x^{\overline{-m}}$ 的定义。）

设 $\Re z$ 和 $\Im z$ 是复数 $z$ 的实部和虚部。其绝对值 $|z|$ 是 $\sqrt{(\Re z)^2+(\Im z)^2}$。当实值的和式 $\sum_{k\in K}\Re a_k$ 和 $\sum_{k\in K}\Im a_k$ 两者都绝对收敛时，就说复数项 $a_k$ 组成的和式 $\sum_{k\in K}a_k$ 绝对收敛。证明：$\sum_{k\in K}a_k$ 绝对收敛，当且仅当存在一个有界常数 $B$，使得对所有的有限子集 $F\subseteq K$，都有 $\sum_{k\in F}|a_k|\leqslant B$。

作业题

利用求和因子来求解递归式 $$ \begin{aligned}&T_0=5~;\\&2T_n=nT_{n-1}+3\times n!~,\quad n>0~.\end{aligned} $$

试用扰动法计算 $\sum_{k=0}^nkH_k$，不过改为推导出 $\sum_{k=0}^nH_k$ 的值。

假设 $n\geqslant0$，用扰动法计算和式 $S_n=\sum_{k=0}^n(-1)^{n-k}$，$T_n=\sum_{k=0}^n(-1)^{n-k}k$ 以及 $U_n=\sum_{k=0}^n(-1)^{n-k}k^2$。

（不用归纳法）证明拉格朗日恒等式：

证明一位逝去 175 年的先人的恒等式是很困难的。

$$ \sum_{1\leqslant j

用两种方法计算和式 $\sum_{k=1}^n(2k+1)/k(k+1)$：

a 用部分分式 $1/k-1/(k+1)$ 替换 $1/k(k+1)$。

b 分部求和法。

$\sum_{0\leqslant k

提示：将 $(2.57)$ 的推导加以推广。

记号 $\prod_{k\in K}a_k$ 表示对所有 $k\in K$ 数 $a_k$ 的乘积。为简单起见，假设仅仅对有限多个 $k$ 有 $a_k\ne1$，因此不必定义无穷乘积。记号 $\Pi$ 满足的法则中，有哪些与对 $\Sigma$ 成立的分配律、结合律以及交换律相类似？

这个记号是雅可比在 1829 年引入的。

通过处理记号 $\Pi$，用单重乘积 $\prod_{k=1}^na_k$ 表示出二重乘积 $P=\prod_{1\leqslant j\leqslant k\leqslant n}a_ja_k$。（本习题给出一个与上三角形恒等式 $(2.33)$ 相似的乘积结果。）

计算 $\Delta(c^{\underline x})$，并用它来推导出 $\sum_{k=1}^n(-2)^{\underline k}/k$ 的值。

下面的推导在何处步入歧途？ $$ \def\ge{\geqslant}\begin{aligned}1=\sum_{k\ge1}\frac1{k(k+1)}&=\sum_{k\ge1}\left(\frac k{k+1}-\frac{k-1}k\right)\\&=\sum_{k\ge1}\sum_{j\ge1}\left(\frac kj[j=k+1]-\frac jk[j=k-1]\right)\\&=\sum_{j\ge1}\sum_{k\ge1}\left(\frac kj[j=k+1]-\frac jk[j=k-1]\right)\\&=\sum_{j\ge1}\sum_{k\ge1}\left(\frac kj[k=j-1]-\frac jk[k=j+1]\right)\\&=\sum_{j\ge1}\left(\frac{j-1}j-\frac j{j+1}\right)=\sum_{j\ge1}\frac{-1}{j(j+1)}=-1~.\end{aligned} $$

考试题

计算和式 $\sum_{k=1}^n(-1)^kk/(4k^2-1)$。

玩 Cribbage 纸牌游戏的人早就知道 $15=7+8=4+5+6=1+2+3+4+5$。求出将 $1050$ 表示成相连的正整数之和的方法数。（将它自身的表示 ”$1050$“ 算作是一种方法，于是，将 $15$ 表示成相连的正整数之和就有四种而不是三种方法。附带指出，了解 Cribbage 纸牌游戏的规则对这个问题没有帮助。）

黎曼 zeta 函数 $\zeta(k)$ 定义为无限和式 $$ 1+\frac1{2^k}+\frac1{3^k}+\cdots=\sum_{j\geqslant1}\frac1{j^k}~. $$ 证明 $\sum_{k\geqslant2}\big(\zeta(k)-1\big)=1$。$\sum_{k\geqslant1}\big(\zeta(2k)-1\big)$ 的值是什么？

令 $a\operatorname∸b=\max(0,a-b)$。证明，对所有实数 $x\geqslant0$ 有 $$ \sum_{k\geqslant0}\min(k,x\operatorname∸k)=\sum_{k\geqslant0}\big(x\operatorname∸\,(2k+1)\big)~, $$ 并用封闭形式计算这些和。

附加题

设 $\Lambda_{k\in K}a_k$ 表示诸数 $a_k$ 中最小者（或者它们的最大下界，如果 $K$ 是无限的），假设每一个 $a_k$ 或者是实数，或者是 $\pm\infty$。对记号 $\Lambda$ 成立的法则中，有哪些与对 $\Sigma$ 以及 $\Pi$ 有效的法则类似（见习题 25）？

丛林法则

证明：如果和式 $\sum_{k\in K}a_k$ 按照 $(2.59)$ 未予定义，那么在下述意义下它是极不寻常的：如果 $A^-$ 和 $A^+$ 是任意给定的实数，有可能找到一个由 $K$ 的有限子集的序列 $F_1\subset F_2\subset F_3\subset\cdots$，使得当 $n$ 为奇数时，$\sum\limits_{k\in F_n}a_k\leqslant A^-$；当 $n$ 为偶数时，$\sum\limits_{k\in F_n}a_k\geqslant A^+$。

证明哥德巴赫定理： $$ 1=\frac13+\frac17+\frac18+\frac1{15}+\frac1{24}+\frac1{26}+\frac1{31}+\frac1{35}+\cdots=\sum_{k\in P}\frac1{k-1}~, $$ 其中 $P$ 是如下用递归方式定义的完全幂（perfect power）组成的集合：

绝对的权力绝对会导致腐败。

英语里 ”幂“ 和 ”权力“ 用的是同一个单词 power，因而 perfect power 恰有双重含义，它可以译为数学中的 ”完全幂“，亦可翻译为政治学中的 ”绝对权力“。在西方政治学中有一句著名的格言：”Absolute power corrupts absolutely.“ 这里的涂鸦 Perfect power corrupts perfectly 系模仿这一名言而来。

$$ P=\big\{m^n~\big|~m\geqslant2,n\geqslant2,m\notin P\big\}~. $$

所罗门 · 哥隆的 ”自描述序列“ $\big\langle f(1),f(2),f(3),\cdots\big\rangle$ 是具有以下性质的仅有的非减正整数序列：对每一个 $k$，$k$ 在其中恰好出现 $f(k)$ 次。稍加思考就会揭示此序列必定以如下形式开始： $$ \def\arraystretch{1.25}\begin{array}{c|llllllllllll}n&1&2&3&4&5&6&7&8&9&10&11&12\\\hline f(n)&1&2&2&3&3&4&4&4&5&5&5&6\end{array} $$ 设 $g(n)$ 是满足 $f(m)=n$ 的最大整数 $m$。证明

a $g(n)=\sum_{k=1}^nf(k)~.$

b $g\big(g(n)\big)=\sum_{k=1}^nkf(k)~.$

c $g\Big(g\big(g(n)\big)\Big)=\dfrac12ng(n)\big(g(n)+1\big)-\dfrac12\sum_{k=1}^{n-1}g(k)\big(g(k)+1\big)~.$