《具体数学》第二章学习笔记：和式

2.1 记号

有确定界限的形式

我们要对一个有确定界限的式子求和：

$$a_1+a_2+\cdots+a_n$$

其中每个 $a_k$ 都是用某种方式定义的一个数。

我们可以用求和符号 $\sum$ 将其表示成这样：

$$\sum\limits_{k=1}^{n}a_k$$

即：

$$\sum\limits_{k=1}^n a_k=a_1+a_2+\cdots+a_n$$

如果难以理解，这里还有其它的一些例子：

$$\sum\limits_{k=0}^{n+1} 2^k=2^0+2^1+\cdots+2^n+2^{n+1}$$

$$\sum\limits_{k=114}^{514}\ln k=\ln 114+\ln 115+\cdots+\ln 513+\ln 514$$

这上面的 $k$ 的含义是指标（index，也可以翻译为编号），它是一个变量，随取值的变化而变化（如果你是 OIer，这应该很好理解），可以用任意字母替换，即：$\sum\limits_{k=0}^{n} a_k$ 与 $\sum\limits_{i=0}^{n} a_i$ 是没有区别的。

另外，$\sum_{k=1}^n a_k$ 与 $\sum\limits_{k=1}^n a_k$ 也是没有区别的，只是这样能使得排版更加美观。。

一般形式

直接把一个或多个条件写在 $\sum$ 下面，以此指定求和所应该取的指标集，例如：

$$\sum\limits_{k=1}^{n} a_k$$

也可以表示为：

$$\sum\limits_{1\leq k\leq n} a_k$$

这种形式更加灵活，打破了只能对连续整数指标求和的限制。例如，我们可以把 $1$ 到 $n$ 之间的质数之和表示为：

$$\sum\limits_{p\leq n\text{且} p \text{是质数}} p$$

同样的，$\sum\limits_{1\leq k\leq n} a_k$ 与 $\sum_{1\leq k\leq n} a_k$ 也是没有区别的。

一种简单的符号

注意，这种写法并不规范，正式考试中最好避免使用

我们把一个命题放在中括号中，当这个命题为真时，其结果为 $1$，当命题为假时，其结果为 $0$。例如：

$$[p \text{是素数}]=\left\{\begin{aligned}1, p \text{是质数}\\0, p \text{是合数}\end{aligned}\right.$$

那么我们就可以把：

$$\sum\limits_{k=1}^{n} a_k$$

表示为：

$$\sum\limits_{k} a_k[1\leq k\leq n]$$

这一表示方式将在某些时候非常好用。

附带提及，求积符号为 $\prod$ ，与 $\sum$ 用法一致。例如：

$$\prod\limits_{k=1}^n a_k=a_1\times a_2\times\cdots\times a_n$$

递归式转和式

对于一个递归式：

$$a_nT_n=b_nT_{n-1}+c_n$$

我们恰当地选取一个求和因子 $s_n$ 满足：

$$s_nb_n=s_{n-1}a_{n-1}$$

用这个因子 $s_n$ 来乘等式两边：

$$s_na_nT_n=s_nb_nT_{n-1}+s_nc_n$$

设 $S_n=s_na_nT_n$，就可以得到：

$$S_n=S_{n-1}+s_nc_n$$

从而：

$$S_n=s_0a_0T_0+\sum\limits_{k=1}^{n}s_kc_k=s_1b_1T_0+\sum\limits_{k=1}^{n}s_kc_k$$

那么：

$$T_n=\frac{1}{s_na_n}(s_1b_1T_0+\sum\limits_{k=1}^n s_kc_k)$$

现在的问题是如何选取一个合适的 $s_n$。

我们可以将 $s_nb_n=s_{n-1}a_{n-1}$ 展开：

$$s_n=\frac{s_{n-1}a_{n-1}}{b_n}=\frac{a_{n-1}a_{n-2}\cdots a_1}{b_nb_{n-1}\cdots b_2}$$

也就是说， $s_n$ 可以选取为这个分式的任意常数倍。

下面仍然是一个例子：

快速排序复杂度

快速排序所做的比较步骤的平均次数满足递归式：

$$\begin{aligned} C_0&=C_1=0;\\ C_n&=\frac{2}{n}\sum\limits_{k=0}^{n-1}C_k+n+1,n>1 \end{aligned}$$

作为一个好习惯，我们先计算出小的情形：$C_2=3,C_3=6,C_4=\frac{19}{2}$。下面是化简：

首先规避除法，在等式两边同时乘上 $n$：

$$nC_n=2\sum\limits_{k=0}^{n-1}C_k+n^2+n,n>1$$

接下来想办法规避 $\sum$ ，我们用 $n-1$ 替换 $n$，就有：

$$(n-1)C_{n-1}=2\sum\limits_{k=0}^{n-2}C_k+(n-1)^2+n-1,n-1>1$$

用第一个方程减去这个方程，就消掉了 $\sum$：

$$nC_n-(n-1)C_{n-1}=2C_{n-1}+2n,n>2$$

于是就化简为了：

$$\begin{aligned} C_0&=C_1=0;C_2=3;\\ nC_n&=(n+1)C_{n-1}+2n,n>2 \end{aligned}$$

显然，这个式子形如：$a_nT_n=b_nT_{n-1}+c_n$ ，其中 $a_n=n,b_n=n+1$。

因此我们要用求和因子

$$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\times 3}=\frac{2}{(n+1)n}$$

的整数倍来遍乘这个递归式。那么它的解就是：

$$C_n=2(n+1)\sum\limits_{k=1}^{n}\frac{1}{k+1}-\frac{2}{3}(n+1),n>1$$

最后出现的这个和式非常常见，因此它有一个特殊的名称和记号：

$$H_n=1+\frac{1}{2}+\cdots+\frac{1}{n}=\sum_{k=1}^n\frac{1}{k}$$

字母 $H$ 表示 Harmonic，即“调和的”，$H_n$ 被称为调和数（Harmonic Number）。

我们尝试用 $H_n$ 来表示 $C_n$

$$\begin{aligned} \sum\limits_{k=1}^n\frac{1}{k+1}&=\sum\limits_{1\leq k\leq n}\frac{1}{k+1}\\ &=\sum\limits_{1\leq k-1\leq n}\frac{1}{k}\\ &=\sum\limits_{2\leq k\leq n+1}\frac{1}{k}\\ &=\Bigg(\sum\limits_{1\leq k\leq n}\frac{1}{k}\Bigg)-\frac{1}{1}+\frac{1}{n+1} \\ &=H_n-\frac{n}{n+1} \end{aligned}$$

那么

$$C_n=2(n+1)H_n-\frac{8}{3}n-\frac{2}{3},n>1$$

2.3 和式的处理

设 $K$ 是任意一个有限整数集合，$K$ 中的元素的和式可以用三条基本变换法则加以交换：

分配律：

$$\sum\limits_{k\in K}ca_k=c\sum\limits_{k\in K} a_k$$

结合律：

$$\sum\limits_{k\in K} (a_k+b_k)=\sum\limits_{k\in K} a_k+\sum\limits_{k\in K} b_k$$

交换律（这里的 $P(k)$ 是这个整数集合的任意一个排列）：

$$\sum\limits_{k\in K} a_k=\sum\limits_{p(k)\in K} a_{p(k)}$$

需要注意的是，这里对三个定律的定义与通常数学书中有很大的区别。

下面是一个例子：

高斯求和

我们要计算一个等差级数的一般和：

$$S=\sum\limits_{0\leq k\leq n}(a+bk)$$

根据交换律，用 $n-k$ 替代 $k$：

$$S=\sum\limits_{0\leq n-k\leq n} (a+b(n-k))=\sum\limits_{0\leq k\leq n} (a+bn-bk)$$

利用结合律将二者相加：

$$2S=\sum\limits_{0\leq k\leq n}((a+bk)+(a+bn-bk))=\sum\limits_{0\leq k\leq n}(2a+bn)$$

利用分配律：

$$2S=(2a+bn)\sum\limits_{0\leq k\leq n} 1=(2a+bn)(n+1)$$

最后除以二，就证明了：

$$\sum\limits_{k=0}^n(a+bk)=\frac{(2a+bn)(n+1)}{2}$$

即小学背的“首项加末项乘项数除以二”。

艾弗森约定

设 $K$ 和 $K'$ 是整数的任意集合，那么：

$$\sum\limits_{k\in K}a_k+\sum\limits_{k\in K'} a_k=\sum\limits_{k\in K\cap K'} a_k+\sum\limits_{k\in K\cup K'}a_k$$

容斥原理的阴影

这是由下面两个一般公式推出的：

$$\sum\limits_{k\in K} a_k=\sum\limits_k a_k[k\in K]$$

$$[k\in K]+[k\in K']=[k\in K\cap K']+[k\in K\cup K']$$

扰动法

扰动法的基础是将一项分离出去，利用它，我们常常可以用封闭形式来计算一个和式，其思想是从一个未知的和式开始，记为 $S_n$：

$$S_n=\sum\limits_{0\leq k\leq n} a_k$$

然后将它的最后一项和第一项分离出来，用两种方法表示 $S_{n+1}$：

$$\begin{aligned} S_n+a_{n+1}&=\sum\limits_{0\leq k\leq n+1} a_k\\ &=a_0 +\sum\limits_{1\leq k\leq n+1} a_k\\ &=a_0+\sum\limits_{1\leq k+1\leq n+1} a_{k+1}\\ &=a_0+\sum\limits_{0\leq k\leq n} a_{k+1} \end{aligned}$$

现在我们可以尝试用 $S_n$ 将最后那个和式表示出来。如果成功，我们就得到一个关于 $S_n$ 的方程。

下面是几个例子：

简单的例子

几何级数的和：

$$S_n=\sum\limits_{0\leq k\leq n} ax^k$$

直接使用刚刚推导的结论：

$$S_n+ax^{n+1}=ax^0 +\sum\limits_{0\leq k\leq n} ax^{k+1}$$

用分配律将右边的和式提出一个 $x$，于是：

$$S_n+ax^{n+1}=ax^0 +\sum\limits_{0\leq k\leq n} ax^{k+1}=ax^0 +x\sum\limits_{0\leq k\leq n} ax^{k}=a+xS_n$$

对 $S_n$ 进行求解，就可以得到：

$$\sum\limits_{0\leq k\leq n} ax^k=\frac{a-ax^{n+1}}{1-x},x\neq 1$$

有点难的例子

$$S_n=\sum\limits_{0\leq k\leq n} k2^k$$

还是可以得到：

$$S_n+(n+1)2^{n+1}=\sum\limits_{0\leq k\leq n} (k+1)2^{k+1}$$

接着使用结合律：

$$\sum\limits_{0\leq k\leq n} (k+1)2^{k+1}=\sum\limits_{0\leq k\leq n} k2^{k+1} +\sum\limits_{0\leq k\leq n} 2^{k+1}$$

这两个和式中第一个等于 $2S_n$，第二个就是几何级数，由“简单的例子”可以知道它等于 $2^{n+2}-2$

因此我们有：

$$S_n+(n+1)2^{n+1}=2S_n+2^{n+2}-2$$

解得：

$$S_n=(n-1)2^{n+1}+2$$

再进一步

如果用 $x$ 代替 $2$，即求：

$$S_n=\sum\limits_{0\leq k\leq n} kx^k$$

用和上面类似的推导可以得到：

$$S_n+(n+1)x^{n+1}=xS_n+\frac{(x-x^{n-2})}{1-x}$$

解之，

$$S_n=\frac{x-(n+1)x^{n+1}+nx^{n+2}}{(1-x)^2},x\neq 1$$

另外，我们还可以使用微积分的初等技巧来推导这个封闭形式。我们在方程：

$$\sum\limits_{k=0}^n x^k=\frac{1-x^{n+1}}{1-x}$$

两边关于 $x$ 求导，就可以得到：

$$\sum\limits_{k=0}^n kx^{k-1}=\frac{(1-x)\big(-(n+1)x^n \big)+1-x^{n+1}}{(1-x)^2}=\frac{1-(n+1)x^n+nx^{n+1}}{(1-x)^2}$$

可以看到，微积分和离散数学有很多的联系。