《具体数学》 2.3 和式的处理

2.3 和式的处理

一、定律

设 $K$ 为任意一个有限整数集合，则有

$$\begin{aligned} \sum_{k\in K}ca_k&=c\sum_{k\in K}a_k &(\texttt{分配律}) \\[6pt]\sum_{k\in K}(a_k+b_k) &= \sum_{k\in K}a_k + \sum_{k\in K}b_k &(\texttt{结合律}) \\[6pt]\sum_{k\in K}a_k&=\sum_{p(k)\in K}a_{p(k)} &(\texttt{交换律}) \end{aligned}$$

需要详细解释的是「交换律」。其中 $p(k)$ 表示一个作用在 $K$ 上的置换。

或者更为宽松的：对于每个 $k$ ，有且仅有唯一的 $p(k)$ 与之对应，且 $p(k)\in K$​​ 。

例如

$$\sum_{k\in K \land k\texttt{是偶数}} a_k = \sum_{n\in K \land n\texttt{是偶数}} a_n = \sum_{2k\in K \land 2k\texttt{是偶数}} a_{2k} = \sum_{2k\in K} a_{2k}$$

---

二、扰动法

本章节提到了扰动法求解未知和式的封闭形式

$$S_n = \sum_{0 \le k\le n}a_k$$

然后通过将它的最后一项和第一项分离出来，用两种方法重新改写 $S_{n+1}$

$$\begin{aligned} S_{n}+a_{n+1} = \sum_{0 \le k\le n+1}a_k &= a_0+\sum_{1\le k \le n+1} a_k \\\\&=a_0+\sum_{1 \le k+1 \le n+1}a_{k+1} \\\\&=a_0+\sum_{0\le k\le n}a_{k+1} \end{aligned}$$

即

$$S_n+a_{n+1}=a_0+\sum_{0\le k\le n}a_{k+1}\tag{1}$$

然后尝试用 $S_n$ 将它表示出来

例子：求一般的几何级数的和

$$S_n = \sum_{0\le k\le n}ax^k$$

由 $(1)$ 中一般的扰动法格式可得

$$S_n + ax^{n+1} = ax^{0}+\sum_{0\le k\le n}ax^{k+1}$$

显然有

$$S_n+ax^{n+1}=ax^0+xS_n$$

故

$$S_n=\dfrac{a-ax^{n+1}}{1-x}$$

---

练习：求下列和式的封闭形式

$$S_n = \sum_{0 \le k \le n}k2^k$$

答案：

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

过程

$$S_n + a_{n+1} = a_0 + \sum_{0 \le k \le n} a_{k+1} \\\\S_n + (n+1)2^{n+1} = 2\sum_{0\le k\le n}k2^k + \sum_{0\le k\le n}2^{k+1} \\\\S_n + (n+1)2^{n+1} = 2S_n + 2^{n+2}-2 \\\\S_n = (n-1)2^{n+1}+2$$