《CM》2.3 Manipulation Of Sums

2.3 Manipulation Of Sums 和的操作

和有3种基本变换规则,分别是:

\begin{array}{l} \sum_{k \in K}ca_k=c\sum_{k \in K}a_k; &\text{(distributive law)}\\ \sum_{k \in K}(a_k+b_k)=\sum_{k \in K}a_k+\sum_{k \in K}b_k; & \text{(associative law)} \\ \sum_{k \in K}a_k=\sum_{p(k) \in K}a_{p(k)}. & \text{(commutative law)}\end{array}

其中K是有限整数集,p(k)是对所有整数的一个排列。这个意思是,对任意整数n,必存在唯一的k使得p(k)=n。也可以换个表达,若有k1和k2且k1≠k2,则有p(k1)≠p(k2)。利用这3条基本规则可以对和进行一系列变换来求出和。由于K是有限集,这里可以对p的约束适当的放松,不必要求是所有整数的排列,只要求对每个属于K中的n,有且仅有唯一的k使得p(k)=n即可。意思是,对不属于K中的整数,不必关心有多少个k使得p(k)映射到这个数,因为它不被包括在和内,对和的结果没有影响。

现在计算

\sum_{k \in K}a_k+\sum_{k \in K'}a_k

根据Iverson的表示法,该式子可以写成

\sum_{k}a_k[k\in K]+\sum_{k}a_k[k\in K']

根据associative law可合成为一个和式

\sum_{k}a_k\left([k \in K]+[k \in K']\right)

由集合知识我们知道

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

由上式及再由associative law分成两个式子,我们得到一个非常重要的结果

\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.

特殊情况下,我们可以把集合K分成\{k_0 \in K\} \cup \{k \neq k_0 | k \in K \},这样我们就得出

\sum_{k \in K}a_k=a_{k_0}+\sum_{\substack{k \in K\\k \neq k_0}}a_k

这种方法叫做perturbation method。亦即我们从一个和中提出固定的一项,再通过一些变换来求出和。更特殊的,提取出首项或末项非常常用。如考虑和

S_n=\sum_{0 \leq k \leq n}a_k.

S_{n+1}写成两种形式,分别提取出首相和末项,我们得到

\begin{array}{l}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{array}

我们需要把最后的和式表示成关于S_n的某种形式,如cS_n,这样我们就可以通过解方程求出S_n

利用perturbation method可以很方便的求出如下几何级数(geometric progression,等比数列)的和:

\sum_{k=0}^n ax^k=\frac{a-ax^{n+1}}{1-x},\quad \text{for }x \neq 1.

现在,考虑如下和

S_n=\sum_{0 \leq k \leq n}k2^k

利用perturbation method,可以得到

S_n+(n+1)2^{n+1}=\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^{n+2}-2

因此,我们得到一个关于S_n的方程,解出S_n,于是,我们求得

\sum_{0 \leq k \leq n}k2^k=(n-1)2^{n+1}+2.

更一般的,可以求出

\sum_{k=0}^nkx^k=\frac{x-(n+1)x^{n+1}+nx^{n+2}}{(1-x)^2},\quad \text{for }x \neq 1.

另外还有一个非常美的方法来求出上式,由

\sum_{k=0}^nx^k=\frac{1-x^{n+1}}{1-x}

两边求导可得

\sum_{k=0}^nkx^{k-1}=\frac{1-(n+1)x^n+nx^{n+1}}{(1-x)^2}

两边再乘以x即为结果。



发表评论

电子邮件地址不会被公开。 必填项已用*标注

*