2.1 记号 NOTATION
和式与项
一般形式的和式 $a_1 + a_2 + \cdots + a_n$
和式的每个元素 $a_k$ 称为项(term)
除了用···来表示和式，我们也可以用（很多时候的确在用）求和符号表示和式
求和符号
自从傅里叶引进 $\sum$ 这个符号代表求和，它就风靡了整个数学界
有确定界形式VS一般形式
一般形式的含义更加清楚。
$$\sum_{k=0}^{49} (2k+1)^2$$
$$\sum_{\stackrel{1 \le k<100}{k是奇数}} k^2$$
这两个求和式是等价的，但后者显然更加清楚易懂
一般形式更加容易处理
$$\sum_{1 \le k \le n}a_k=\sum_{1 \le k+1 \le n}a_{k+1} $$
$$ \sum_{k=1}^n a_k=\sum_{k=0}^{n-1}a_{k+1} $$
相同的变换，第一个式子使用一般形式，几乎不需要思考就可以做出这样的代换；第二个等式的转换就有点不容易看出来，也容易出错。
在这里使用 $k$ 而不是 $i$ 作为指标变量，因为 $i$ 还有更重要的任务，代表 $\sqrt{-1}$
更一般的形式
$$ \sum_{P(k)}a_k $$
其中，$k$是满足性质$P(k)$的一个整数
不加限定条件的表示和式
艾弗森在它的程序语言APL中提出一个思想：我们可以把一个为真或为假的命题放在括号中，如$[p是素数]$，其结果是1或0。
所以，我们就可以不加限制条件的表示和式
$$\sum_p [p是素数][p \le N]/p$$
这个和式表示 $\le N$ 的素数倒数之和
2.2 和式与递归式 SUMS AND RECURRENCES
和式转化为递归式
如何来求和式的值呢？一种方法是观察和式与递归式之间存在的密切关系。和式
$$S_n=\sum_{k=0}^na_k$$
等价于递归式
$$\begin{array}{} S_0 &=a_0 \\ S_n &= S_{n-1}+a_n ,\quad n>0 \end{array} \tag{2.6}$$
这样，就可以利用第一章学到的用封闭形式求解递归式的方法。再来复习一下：
例如，如果$a_n$等于一个常数加上$n$的倍数，那么和式-递归式(2.6)的一般形式犹如
$$\begin{array}{} R_0 &=\alpha \\ R_n &= R_{n-1}+\beta+\gamma n ,\quad n>0 \end{array} \tag{2.7}$$一般来说，它的解可以写成形式
$$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$
于是，如果我们想要计算$\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{array}{} T_0 &=0 \\ T_n &= 2T_{n-1}+1 ,\quad n>0 \end{array}$$
如果两边都用$2^n$来除，它就可以写成
$$\begin{array}{} T_0/2^0 &=0 \\ T_n/2^n &= T_{n-1}/2^{n-1}+1/2^n ,\quad n>0 \end{array}$$
现在令$S_n=T_n/2^n$，我们就有
$$\begin{array}{} S_0 &=0 \\ S_n &= S_{n-1}+2^{-n} ,\quad n>0 \end{array}$$
由此得到
$$S_n=\sum_{k=1}^n$$
几何级数的和$$2^{-1}+2^{-2}+\cdots+2^{-n}=1-\left(\frac{1}{2}\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}$$
的递归式转换成一个和式。**其思想在于用一个求和因子$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=\frac{1}{s_na_n}\left(s_1b_1T_0+\sum_{k=1}^ns_kc_k\right)\tag{2.10}$$
但是，我们怎样才能求出正确的$s_n$呢？没问题，关系式$s_n=s_{n-1}a_{n-1}/b_n$可以被展开，从而我们发现，分式
$$s_n=\cfrac{a_{n-1}a_{n-2}\cdots a_1}{b_{n}b_{n-1}\cdots b_2}\tag{2.11}$$
或者这个值的任何适当的常数倍，会是一个合适的求和因子。注意不要用0做除数，所以只要所有的$a$和$b$都不为零，那么求和因子方法就能奏效
另一个例子
我们来把上面的探索结果应用到“快速排序”中所出现的递归式。排序$n$个元素的随机序列时，快速排序所做的比较操作的平均次数满足递归式
$$\begin{array}{} C_0&=&C_1=0 \\ C_n&=& n+1+\cfrac{2}{n}\sum_{k=0}^{n-1}C_k ,\quad n>1 \end{array}\tag{2.12}$$
这个递归式看起来十分复杂，它含有一个对前面的值求和的和式。我们可以系统地来化简(2.12)的复杂性，首先避免除法，然后再规避掉符号$\sum$。用$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{array}{} C_0&=C_1=0; \quad C_2=3 \\ nC_n&=(n+1)C_{n-1}+2n ,\quad n>2 \end{array}$$
这个递归式形如(2.9)，其中$a_n=n$,$b_n=n+1$，且
$$c_n=2n-2[n=1]+2[n=2]$$
故而我们现在能用求和因子方法。前面介绍的一般方法告诉我们，要用
$$s_n=\cfrac{a_{n-1}a_{n-2}\cdots a_1}{b_{n}b_{n-1}\cdots b_2}=\cfrac{(n-1)\times(n-2)\times\cdots\times 1}{(n+1)\times n\times 3}=\cfrac{2}{(n+1)n}$$的某个倍数来遍乘该递归式。根据(2.10)，它的解就是
$$C_n=2(n+1)\sum_{k=1}^n \cfrac{1}{k+1}-\cfrac{2}{3}(n+1),\quad n>1$$
这个和式中有一个量和应用中频繁出现的一个量极为相似———调和数
$$H_n=1+\cfrac12+\cdots+\cfrac1n=\sum_{k=1}^n \cfrac1k\tag{2.13}$$
我们可以利用$H_n$将$C_n$写成封闭形式：
$$\begin{array}{}
\sum\limits_{1\le k\le n}\cfrac{1}{k+1}&=&\sum\limits_{1\le k-1\le n}\cfrac{1}{k} \\
&=&\sum\limits_{2\le k\le n+1}\cfrac{1}{k} \\
&=&\left(\sum\limits_{1\le k\le n}\cfrac{1}{k}\right)-\cfrac11+\cfrac{1}{n+1} \\
&=&H_n-\cfrac{n}{n+1}
\end{array}
$$
所以$$C_n=2(n+1)H_n-\cfrac83 n-\cfrac23,\quad n>1$$
2.3 和式的处理 MANIPULATION OF SUMS
成功处理和式的关键在于，将一个$\sum$改变成一个更简单或更接近目标的$\sum$。学习一些基本的变换法则，就会很容易做到这一点。
基本变换法则
设$K$是任意一个有限整数集合。$K$中元素的和式可以用三条简单的法则加以变换：
$$\sum\limits_{k\in K}ca_k=c\sum\limits_{k\in K}a_k \qquad \text{(分配律)}\tag{2.15}$$
$$\sum\limits_{k\in K}(a_k+b_k)=\sum\limits_{k\in K}a_k+\sum\limits_{k\in K}b_k \qquad \text{(结合律)}\tag{2.16}$$
$$\sum\limits_{k\in K}a_k=\sum\limits_{p(k)\in K}a_{p(k)} \qquad \text{（交换律）} \tag{2.17}$$
运用分配律，我们能把常数移入和移出$\sum$；运用结合律，我们可以把一个$\sum$分成两个部分；运用交换律，我们可以按照愿意采用的任何方式来重新将求和项排序，这里$p(k)$是所有整数集合的任意一个排列。
一个例子：求等差级数的一般和
假设我们要计算一个等差级数的一般和：
$$S=\sum\limits_{0\le k\le n}(a+bk)$$根据交换律，我们可以用$n-k$代替$k$，得到$$S=\sum\limits_{0\le n-k\le n}(a+b(n-k))=\sum\limits_{0\le k\le n}(a+bn-bk)$$利用结合律，可以把这两个方程相加$$2S=\sum\limits_{0\le k\le n}((a+bk)+(a+bn-bk))=\sum\limits_{0\le k\le n}(2a+bn)$$现在利用分配律$$2S=(2a+bn)\sum\limits_{0\le k\le n}1=(2a+bn)(b+n)$$故我们就证明了$$\sum\limits_{k=0}^n(a+bk)=(a+\frac{1}{2}bn)(n+1) \tag{2.18}$$
其他
在一般的交换律(2.17)中的函数$p(k)$都假设是所有整数的排列。即对每个整数$n$，都恰好存在一个整数$k$，使得$p(k)=n$。现在，我们将排列限制稍稍放松。我们只需要求，当$n$是指标集$K$中的一个元素时，恰好有一个整数$k$满足$p(k)=n$，而不关心那些不在$K$中的$n$。
例如，由于当$n\in K$且$n$是偶数时恰好有一个$k$使得$2k=n$，故可以进行以下推导：$$\sum\limits_{\substack{k\in K \\ k是偶数 }}a_k=\sum\limits_{\substack{n\in K \\ n是偶数 }}a_n=\sum\limits_{\substack{2k\in K \\ 2k是偶数 }}a_{2k}=\sum\limits_{2k\in K}a_{2k}$$
通过公式中间的逻辑命题来得到0或者1的艾佛森约定，可以与分配律、结合律以及交换律一起使用，以导出和式的其他性质。下面就是一个常用的性质：如果$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{0\le k\le n}a_k=a_0+\sum\limits{1\le k\le n}a_k,\quad n\ge 0$$
把一项分出去的运算是扰动法的基础，利用扰动法，我们常常可以用封闭形式来计算一个和式。其思想是从一个未知的和式开始，并记它为$S_n$：$$S_n=\sum\limits_{0\le k\le n}a_k$$然后，通过将它的最后一项和第一项分离出来，用两种方法重新改写$S_{n+1}$：$$\begin{array}{}
S_n+a_{n+1}=\sum\limits_{0\le k\le n+1}a_k&=&a_0+\sum\limits_{1\le k\le n+1}a_k \\
&=&a_0+\sum\limits_{0\le k+1\le n+1}a_{k+1} \\
&=&a_0+\sum\limits_{0\le k\le n}a_{k+1}
\end{array}\tag{2.24}$$
一个例子：求几何级数的一般和
$$S_n=\sum\limits_{0\le k\le n}ax^k$$
利用扰动法，则有
$$S_n+ax^{n+1}=ax^0+\sum\limits_{0\le k\le n}ax^{k+1}$$