具体数学-和式

数学中处处都有和式，所以我们需要一些基本的工具来处理它们。

一、记号 Notation

我们将研究一般形式的和：

    a_{1}+a_{2}+…+a_{n}

其中每个 a_{k} 都是用某种方式定义的一个数。这一记号的优点是，如果我们有足够好的想象力，就可以看见“整个”和，就像能把它完整地写出来一样。和式的每个元素 a_{k} 称为项(term)。但是，这个三点记号可能含糊不清且有点冗长累赘。还可以用其他方式，尤其是有确定界限的表达式

    \displaystyle\sum_{k=1}^{n}a_{k}

它称为 \sum 符号，因为用到希腊字母\sum(大写的\sigma).这个记号告诉我们。这个和式中正好包含其指标 k 取介于下限 1 和上限 n 之间(上下限包含在内)的整数的哪些项a_{k}。换句话说“我们对 k 从 1 到 n 求和”。附带提及，\sum 后面的量(这里是a_{k})称为被加数(summand)。指标变量 k 被认为是与和式中 \sum 符号密切相关的，因为 a_{k} 中的 k 与 \sum 符号外出现的 k 无关。任何其它字母都可以替代这里的 k 而不会改变该和式的含义。常常会使用字母 i[似乎因为它代表了“指标”(index)]，不过我们一般还是对 k 进行求和，因为 i 另有重任，要表示 \sqrt{-1}。
一种推广的\sum符号的一般形式甚至比有确定界限的形式更加有用：我们直接把一个或多个条件写在\sum下面，上面的和式还可以写成

    \displaystyle\sum_{1 \le k \le n}a_{k}

这种方式表示的最大好处是比确定有界形式更容易处理。例如要将指标变量k改变成k+1。由一般形式我们就有

    \displaystyle\sum_{1 \le k \le n}a_{k} = \displaystyle\sum_{1 \le k+1 \le n}a_{k+1}

我们几乎不需要思考就能做出这样的代换，但对于有确定界限的形式，就有

    \displaystyle\sum_{k=1}^{n}a_{k} = \displaystyle\sum_{k=0}^{n-1}a_{k+1}

不容易看出它发生了什么变化，而且更容易犯错误。
进一步的，形式上，我们将

    \displaystyle\sum_{p(k)}a_{k}

记为所有a_{k}之和的缩写，其中k是满足给定性质p(k)的一个整数。

肯尼斯·艾弗森记号(Kenneth E. Iverson)

Kenneth E. Iverson在他的程序语言APL中引入了一个奇妙的思想，我们将会看到，这一思想将会极大简化我们接下来的许多事情。例如

    [p是素数]
    \begin{cases}
    1,  & \text{$p$是素数} \\
    0, & \text{$p$不是素数}
\end{cases}

这就意味着，我们有了一种新的表达和式的方式

    \displaystyle\sum_{p(k)}a_{k} = \displaystyle\sum_{k}a_{k}[p(k)]

二、和式和递归式 Sums And Recurrences

好了，现在我们知道如何用特定的符号表示和式了，那么又如何来求和式呢？一种方法是观察和式与递归式之间存在的关系。和式

    S_{n} = \displaystyle\sum_{k=0}^{n}a_{k}

等价于递归式

\begin{alignedat}{1}
    S_{0} &= a_{0} \\
    S_{n} &= S_{n-1} + a_{n},n>0
\end{alignedat}

这样一来，我们就可以使用成套方法来得到这个递归式的封闭形式。

例如，如果a_{n}等于一个常数加上n的一个倍数，那么和式-递归式的一般形式就是

\begin{alignedat}{1}
    R_{0} &= \alpha \\
    R_{n} &= R_{n-1} + \beta + \gamma n,n>0
\end{alignedat}

所以它的解可以写成

    R_{n} \equiv A(n)\alpha+B(n)\beta+C(n)\gamma.

分别令R(n) = 1,R(n) = n,R(n) = n^2,可以求出

\begin{alignedat}{1}
    A(n) &= 1 \\
    B(n) &= n \\
    C(n) &= \frac{n^2+n}{2}
\end{alignedat}

于是，下面和式的计算就非常简单了

\begin{alignedat}{1}
    \displaystyle\sum_{k=0}^{n}(a+bk) &= aA(n)+aB(n)+bC(n) \\
    &=a + an + \frac{(n^2+n)b}{2}
\end{alignedat}

反过来，许多递归式也可以转换成和式来进行计算，比如河内塔(汉诺塔)

\begin{alignedat}{1}
    T_{0} &= 0 \\
    T_{n} &= 2T_{n-1} + 1,n>0
\end{alignedat}

两边用2^n来除，就有

\begin{alignedat}{1}
    \frac{T_{0}}{2^0} &= 0 \\
    \frac{T_{n}}{2^n} &= \frac{T_{n-1}}{2^{n-1}} + \frac{1}{2^n},n>0
\end{alignedat}

令S_{n}=T_{n}/2^n,我们有

\begin{alignedat}{1}
    S_{0} &= 0 \\
    S_{n} &= S_{n-1} + 2^{-n},n>0
\end{alignedat}

由此得到

    S_{n} = \displaystyle\sum_{k=1}^{n}2^{-k} = 1 - (\frac{1}{2})^n

所以

    T_{n} = 2^nS_{n} = 2^n - 1

实际上，一般技术可以将任何形如

    a_{n}T_{n} = b_{n}T_{n-1} + c_{n}

的递归式转化成一个和式。其思想在于用一个求和因子 (summation factor)s_n来乘两边

    s_{n}a_{n}T_{n} = s_{n}b_{n}T_{n-1} + s_{n}c_{n}

因子s_{n}需要恰当的选取，以使得

    s_{n}b_{n} = s_{n-1}a_{n-1}

这样一来，如果记S_{n}=s_{n}a_{n}T_{n},就有

    S_{n} = S_{n-1}+s_{n}c_{n}

从而

    S_{n} = s_{0}a_{0}T_{0} + \displaystyle\sum_{k=1}^{n}s_{k}c_{k} = s_{1}b_{1}T_{0} + \displaystyle\sum_{k=1}^{n}s_{k}c_{k}

所以，原来递归式的解就是

    T_{n} = \frac{1}{s_{n}a_{n}} (s_{1}b_{1}T_{0} + \displaystyle\sum_{k=1}^{n}s_{k}c_{k})

但是，我们怎样才能有足够的智慧求出正确的s_{n}呢？没有问题：关系式s_{n}=s_{n-1}a_{n-1}/b_{n}可以被展开

     s_{n} = \frac{a_{n-1}a_{n-2}…a_1}{b_{n}b_{n-1}…b_2}

注意，这里的s_1的值消去了。实际上可以从中消去(截断)任何一个m，就是说到s_m就消去。只要所有的a和b都不为零，那么求和的方法总能奏效。

快速排序的平均比较次数的计算

快速排序的平均比较次数满足如下递归式

\begin{alignedat}{1}
C_0 &= C_1 = 0 \\
C_n &= n+1+\frac{2}{n}\displaystyle\sum_{k=0}^{n-1}C_k,n>1
\end{alignedat}

首先，为了避免除法，两边同时乘n

nC_n = n^2+n+2\displaystyle\sum_{k=0}^{n-1}C_k,n>1

为了避免\sum符号，我们用n-1代替n

(n-1)C_{n-1} = n^2-n+2\displaystyle\sum_{k=0}^{n-2}C_k,n-1>1

两式相减

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

这样我们就有

\begin{alignedat}{1}
C_0 &= C_1 = 0 \\
C_2 &= 3 \\
C_3 &= 6 \\
nC_n &= (n+1)C_{n-1} +2n,n>2
\end{alignedat}

根据此式，我们可以计算出s_n

\begin{alignedat}{1}
    s_n &= \frac{a_{n-1}a_{n-2}…a_1}{b_{n}b_{n-1}…b_2} \\
    &= \small \frac{(n-1)(n-2)…(1)}{(n+1)(n)…(3)} \\
    &= \small \frac{2}{(n+1)n}
\end{alignedat}

两边同乘s_n

\frac{2}{n+1}C_n = \frac{2}{n}C_{n-1} + \frac{4}{n+1},n>2

令T_n = 2C_n/(n+1),有

T_n = T_{n-1} + \frac{4}{n+1},n>2

又因为，我们有T_3 = 3,所以

\begin{alignedat}{1}
T_n &= T_{3} + \displaystyle\sum_{k=4}^{n}\frac{4}{k+1},n>3 \\
T_n &= 3 + 4\displaystyle\sum_{k=4}^{n}\frac{1}{k+1},n>3
\end{alignedat}

所以

\begin{alignedat}{1}
C_0 &= C_1 = 0 \\
C_2 &= 3 \\
C_3 &= 6 \\
C_n &= \frac{3}{2}(n+1) + 2(n+1)\displaystyle\sum_{k=4}^{n}\frac{1}{k+1},n>3
\end{alignedat}

三、和式的处理 Manipulation Of Sums

设K是任意一个有限整数集合。K中元素的和式可以用三条简单的法则加以变换：

\begin{alignedat}{2}
\displaystyle\sum_{k \in K}ca_k &= c\displaystyle\sum_{k \in K} a_k,& (分配律) \\
\displaystyle\sum_{k \in K}(a_k+b_k) &= \displaystyle\sum_{k \in K}a_k + \displaystyle\sum_{k \in K}b_k,&(结合律) \\
\displaystyle\sum_{k \in K}a_k &= \displaystyle\sum_{k \in p(k)}a_{p(k)},&(交换律)
\end{alignedat}

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

\displaystyle\sum_{0 \le k \le n}(a+bk)

根据交换律，我们可以用n-k代替k，得到

\displaystyle\sum_{0 \le k \le n}(a+bk) = \displaystyle\sum_{0 \le n-k \le n}(a+bn-bk) = \displaystyle\sum_{0 \le k \le n}(a+bn-bk)

利用结合律，将这两个方程相加

2S = \displaystyle\sum_{0 \le k \le n}((a+bn-bk) + (a+bk)) = \displaystyle\sum_{0 \le k \le n}(2a+bn)

现在利用分配律

2S = (2a+bn)\displaystyle\sum_{0 \le k \le n}1 = (2a+bn)(n+1)

所以

S = (2a+bn)(n+1)/2

重要的是要记住，在一般的交换律p(k)都假设是所有整数的排列。换句话说，对每个整数n，都恰好存在一个整数k，使得p(k) = n。否则交换律可能不成立。这里有一个例子恰好能够说明这一情况：将下列两个和式展开

\displaystyle\sum_{0 \le k \le 5}a_k,\displaystyle\sum_{0 \le k^2 \le 5}a_{k^2}

第一个和式非常简单

\displaystyle\sum_{0 \le k \le 5}a_k = a_0+a_1+a_2+a_3+a_4+a_5

第二个和式比较棘手，它是

\displaystyle\sum_{0 \le k^2 \le 5}a_{k^2} = a_4+a_1+a_0+a_1+a_4

我们可以发现，此时的交换律并不成立。

另一方面，我们能将排列限制稍微放松一点点

\displaystyle\sum_{k是偶数}a_{k} =\displaystyle\sum a_{2k}

根据艾弗森约定

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

我们可以得到

\displaystyle\sum_{k \in K}a_{k} + \displaystyle\sum_{k \in M}a_{k} =  \displaystyle\sum_{k \in K \cap M}a_{k} + \displaystyle\sum_{k \in K \cup M}a_{k}

扰动法(Perturbation Method)

把一项分出去的运算是扰动法的基础，利用扰动法，我们常常可以用封闭形式来计算一个和式，例如

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

分离第一项和最后一项

\begin{alignedat}{2}
S_n + a_{n+1} = a_0+\displaystyle\sum_{0 \le k \le n}a_{k+1}
\end{alignedat}

下面我们运用这一方法来计算几何级数的和

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

利用扰动法

\begin{alignedat}{2}
S_n + ax^{n+1} &= a + \displaystyle\sum_{0 \le k \le n}ax^{k+1} \\
&= a + x\displaystyle\sum_{0 \le k \le n}ax^k \\
&= a + xS_n
\end{alignedat}

这样我们就能解出S_n，只要x不为1

S_n  = \large \frac{a - ax^{n+1}}{1-x}