03 MANIPULATION OF SUMS

成功处理和式的关键在于将一个$\sum$改变成一个更简单或者更接近某个目标的$\sum$。通过学习一些基本的变化法则并实践，很容易做到这一点。
设$K$是任意一个有限整数集合。$K$中元素的和式可以用下面三条简单的法则进行变换。 $$\begin{aligned} \sum_{k\in K}ca_k&=c\sum_{k\in K}a_k&&&(2.15)\\ \sum_{k\in K}(a_k+b_k)&=\sum_{k\in K}a_k+\sum_{k\in K}b_k&&&(2.16)\\ \sum_{k\in K}a_k&=\sum_{p(k)\in K}a_{p(k)}&&&(2.17) \end{aligned}$$ 运用分配律（第一个等式）可以把常量移入或移出$\sum$；运用结合律（第二个等式）可以把一个$\sum$分成两个部分，或者把两个$\sum$组合成一个；运用交换律（第三个等式）可以按照任意顺序来求和，这里的$p(k)$是所有整数集合的任意一个排列。例如，假设$K=\{-1,0,1\}, p(k)=-k$，运用这三条法则就有： $$ca_{-1}+ca_{0}+ca_{1}=c(a_{-1}+a_0+a_1)$$ $$(a_{-1}+b_{-1})+(a_0+b_0)+(a_1+b_1)=(a_{-1}+a_0+a_1)+(b_{-1}+b_0+b_1)$$ $$a_{-1}+a_0+a_1=a_1+a_0+a_{-1}$$

第一章中的高斯技巧可以看作是这三个法则的一个应用。假设要计算一个等差数列的和 $$S=\sum_{0\leq k\leq n}(a+bk)$$ 根据交换律可以用$n-k$替代$k$，得到 $$S=\sum_{0\leq n-k\leq n}(a+b(n-k))=\sum_{0\leq k\leq n}(a+bn-bk)$$ 利用结合律将两式相加 $$2S=\sum_{0\leq k\leq n}(a+bk+a+bn-bk)=\sum_{0\leq k\leq n}(2a+bn)$$ 利用分配律得到 $$2S=(2a+bn)\sum_{0\leq k\leq n}1=(2a+bn)(n+1)$$ 两边除以2得到 $$S=(a+\frac{1}{2}bn)(n+1)\tag{2.18}$$

重要的是要理解，$(2.17)$中的$p(k)$是所有整数的排列。对于每一个$n$，都恰好有一个$k$使得$p(k)=n$，否则交换律不成立。习题3以极端例子对此作了描述，比如$p(k)=c+k$或者$p(k)=c-k$这种总是一种排列。
另一方面，我们可以对排列稍稍放宽一些限制。当$n$是指标集$K$的元素时，恰好有一个$p(k)=n$，如果$n\notin K$时，那么$p(k)=n$出现多少次都可以，因为$k$不会出现在和式中。例如，当$n\in K$时且$n$是偶数，那么恰好有$k$使得$2k=n$，我们可以说 $$\sum_{k\in K, k \text{even}}a_k=\sum_{n\in K, n \text{even}}a_n=\sum_{2k\in K, 2k \text{even}}a_{2k}=\sum_{2k\in K}a_{2k}\tag{2.19}$$

通过公式中间的逻辑命题来得到0或者1的艾弗森约定，可以与分配律、结合律以及交换律一起使用，导出和式的其他性质。下面是将不同指标集合组合在一起的一个重要法则。如果$K,K'$是整数的任意集合，那么 $$\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_{k}a_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}$$ 利用$(2.20)$把可以把两个几乎不相交的和式合并起来 $$\sum_{k=1}^ma_k+\sum_{k=m}^na_k=a_m+\sum_{k=1}^na_k$$ 或者把求和的单独一项移出去 $$\sum_{0\leq k\leq n}a_k=a_0+\sum_{1\leq k\leq n}a_k,n\geq 1\tag{2.23}$$ 把一项单独移出去是扰动法（perturbation method）的基础。利用这个方法，我们计算和式的封闭形式。从和式$S_n$开始 $$S_n=\sum_{0\leq k\leq n}a_k$$ 然后通过分离第一项和最后一项，用两种方法来重写$S_{n+1}$ $$\begin{aligned} S_n+a_{n+1}=\sum_{0\leq k\leq n+1}a_k&=a_0+\sum_{1\leq k\leq n+1}a_k\\ &=a_0+\sum_{1\leq k+1\leq n+1}a_{k+1}\\ &=a_0+\sum_{0\leq k\leq n}a_{k+1} \end{aligned}\tag{2.24}$$ 我们可以对最后一个和式进行处理，写成$S_n$的形式，那么就会得到一个方程，进而求得和式的形式。

我们可以用这个方法计算一般的几何级数的和 $$S_n=\sum_{0\leq k\leq n}ax^k$$ 根据$(2.24)$，有 $$S_n+ax^{n+1}=ax^0+\sum_{0\leq k\leq n}ax^{k+1}$$ 根据分配律，右边的和式可以等于$x\sum_{0\leq k\leq n}ax^{k}=xS_n$。所以 $$S_n+ax^{n+1}=a+xS_n$$ 这是关于$S_n$的方程，所以 $$S_n=\frac{a-ax^{n+1}}{1-x},x\neq 1\tag{2.25}$$ 当$x=1$时，和就是$(n+1)a$。右边可以看作是和式的第一项减去此级数之外的第一项（级数最后一项的后一项），再除以1减去公比。

我们再看一个稍难得例子。 $$S_n=\sum_{0\leq k\leq 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}=0+\sum_{0\leq k\leq n}(k+1)2^{k+1}$$ 借助结合律把右边的和式写作两个和式 $$\sum_{0\leq k\leq n}k2^{k+1}+\sum_{0\leq k\leq 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\leq k\leq n}k2^k=S_n=(n-1)2^{n+1}+2$$ 这就能理解为什么$S_3=34$，它等于$32+2$。
用$x$替代2，类似的推导可以得到 $$S_n+(n+1)x^{n+1}=xS_n+(x-x^{n+2})/(1-x)$$ 继而可以得到 $$\sum_{0\leq k\leq n}kx^k=\frac{x-(n+1)x^{n+1}+nx^{n+2}}{(1-x)^2},x\neq 1\tag{2.26}$$

我们可以用完全不同的方式得到类似的结果。利用微积分的求导。如果我们从方程 $$\sum_{0\leq k\leq n}x^k=\frac{1-x^{n+1}}{1-x}$$ 开始，两边对$x$求导，得到 $$\begin{aligned} \sum_{0\leq k\leq n}kx^{k-1}&=\frac{(1-x)(-(n+1)x^n)+1-x^{n+1}}{(1-x)^2}\\ &=\frac{1-(n+1)x^n+nx^{n+1}}{(1-x)^2} \end{aligned}$$ 两边再乘$x$就是$(2.26)$了。
因为和式的导数等于各项导数的和。后续几章会看到微积分和离散数学之间更多的联系。