02 SUMS AND RECURRENCES

如何求和式的值呢？一种是观察和式与递推式之间的关系。和式 $$S_n=\sum_{k=0}^na_k$$ 等价于递归式 $$\begin{aligned} S_0&=a_0\\ S_n&=S_{n-1}+a_n, n>0 \end{aligned}\tag{2.6}$$ 这样利用第一章学习的求递归式的封闭形式的方法来求解。
比如$a_n$是一个常数加上$n$的常量倍，那么$(2.6)$的一般形式就可以具化为 $$\begin{aligned} R_0&=\alpha\\ R_n&=R_{n-1}+\beta+\gamma n,n>0 \end{aligned}\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$的。 现在使用成套方法来求解这个问题。首先令$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$，所以 $$n^2=-B(n)+2C(n)=2C(n)-n$$ 那么 $$C(n)=\frac{n^2+n}{2}$$ 如果我们想要计算 $$\sum_{k=0}^n(a+bk)$$ 那么$(2.7)$中$\alpha=a,\beta=a,\gamma=b$，所以 $$R_n=aA(n)+aB(n)+bC(n)=a(n+1)+b(n+1)n/2$$

反过来看，很多递推式可以转化成求和式，所以后续学习的计算和式的方法也可以用于求递归式。回顾汉诺塔的例子 $$\begin{aligned} T_0&=0\\ T_n&=2T_{n-1}+1,n>0 \end{aligned}$$ 两边同除$2^n$得到 $$\begin{aligned} T_0/2^0&=0\\ T_n/2^n&=2T_{n-1}/2^n+1/2^n,n>0 \end{aligned}$$ 令$S_n=T_n/2^n$，那么有 $$\begin{aligned} S_0&=0\\ S_n&=S_{n-1}+1/2^n,n>0 \end{aligned}$$ 所以 $$S_n=\sum_{k=1}^n2^{-k}$$ 上面式子没有包含$k=0$，因为$S_0=0$而不是$2^{-0}=1$。上面的式子本质上是几何级数求和 $$2^{-1}+2^{-2}+\cdots+2^{-n}=1-2^{-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}$$ 的递归式转化为求和的式子。核心思想在于用一个求和因子（summation factor）$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}(s_1b_1T_0+\sum_{k=1}^ns_kc_k)\tag{2.10}$$ 例如$n=1$时，那么$T_1=(s_1b_1T_0+s_1c_1)/s_1a_1=(b_1T_0+c_1)/a_1$。
但是，如何找到$s_n$呢？观察关系式$s_nb_n=s_{n-1}a_{n-1}$，展开得到 $$s_n=\frac{a_{n-1}a_{n-2}\cdots a_1}{b_nb_{n-1}\cdots b_2}$$ $s_n$或者是这个值的任何适当的常数倍都可以作为因子。回到汉诺塔问题，$a_n=1,b_n=2$，$s_n=2^{-n}$就是一个好的因子。直接应用公式得到的$s_n$是$2^{n-1}$也可以用的，这时$S_n=T_n/2^{n-1}$。
这里需要注意的是除数不能为零，只要$a,b$不全是零，这个方法就能奏效。

现在我们把这种技术应用到分析快排算法的性能分析中。如果是$n$待排的项，那么平均比较次数的递归公式如下： $$\begin{aligned} C_0&=C_1=0\\ C_n&=n+1+\frac{2}{n}\sum_{k=0}^{n-1}C_k,n>1 \end{aligned}\tag{2.12}$$ 这个递归式看起来比之前的复杂很多。尝试一些小的数据，$C_2=3,C_3=6,C_4=\frac{19}{2}$，貌似也没有帮助。
我们可以系统性的消除$(2.12)$的复杂性，首先消除除法，接着消除$\sum$。两边同乘$n$得到 $$nC_n=n^2+n+2\sum_{k=0}^{n-1}C_k,n>1$$ 使用$n-1$替代$n$ $$(n-1)C_{n-1}=(n-1)^2+(n-1)+2\sum_{k=0}^{n-2}C_k,n-1>1$$ 第一个式子减去第二个式子消除$\sum$ $$nC_n-(n-1)C_{n-1}=2n+2C_{n-1},n>2$$ 这样，原来的$C_n$递归式转化成了一个简单的多的递归式 $$C_0=C_1=0; C_2=3;$$ $$nC_n=(n+1)C_{n-1}+2n,n>2$$ 对应到式子$(2.9)$有$a_n=n,b_n=n+1$，且 $$c_n=2n-2[n=1]+2[n=2]$$ 对于$n>2$，$c_n=2n$是显然的。$n=2$时，$2C_2=6=1C_1+c_2=c_2$，那么$c_2=6=2\times 2+2$；$n=1$时，$C_1=0=0C_0+c_1=c_1=0=2\times 1-2$。
用前面推导的求和因子公式 $$s_n=\frac{a_{n-1}a_{n-2}\cdots a_1}{b_nb_{n-1}\cdots b_2}=\frac{(n-1)(n-2)\cdots (2)(1)}{(n+1)(n)\cdots (3)}=\frac{2}{n(n+1)}$$ 根据公式$(2.10)$， $$C_n=2(n+1)\sum_{k=1}^n\frac{1}{k+1}-\frac{2}{3}(n+1),n>1$$ 现在推导下后面的部分是哪里来的。因为直接套用$(2.10)$是没有这个尾巴的，因为$C_1=0$。注意这里最后写的是$n>1$，但是递归的地方写的是$n>2$，那么可以写作 $$\begin{aligned} C_n&=2(n+1)\sum_{k=2}^n\frac{1}{k+1}+(n+1)-\frac{2}{3}(n+1)\\ &=2(n+1)\sum_{k=2}^n\frac{1}{k+1}+\frac{1}{3}(n+1) \end{aligned},n>1$$ 还是有一个尾巴。前面推导的时候我们认为$c_n$是一个简单的公式，比如$c_n=2n$，但是$c_2=6$，比公式推导的时候多了2，所以需要加上 $$\frac{1}{s_na_n}s_2\Delta_{c_2}=\frac{n+1}{2}(\frac{1}{3})(2)=\frac{1}{3}(n+1)$$ 最后这个公式中的和式和某个应用中频繁出现的量很像。它就是调和数（harmonic number），定义如下： $$H_n=1+\frac{1}{2}+\cdots+\frac{1}{n}=\sum_{k=1}^n\frac{1}{k}\tag{2.13}$$ 之所以这样命名，是因为小提琴第$k$个泛音（harmonic）是弦$1/k$处产生的基音。
现在考虑用$H_n$来表示$C_n$，我们现在处理$C_n$中的和式，需要修改边界条件使得$k+1$变成$k$ $$\begin{aligned}\sum_{1\leq k\leq n}\frac{1}{k+1}&=\sum_{1\leq k-1 \leq n}\frac{1}{k}\\ &=\sum_{2\leq k \leq n+1}\frac{1}{k}\\ &=\sum_{1\leq k \leq n}\frac{1}{k}-\frac{1}{1}+\frac{1}{n+1}\\ &=H_n-\frac{n}{n+1}\end{aligned}$$ 那么$C_n$就可以记作 $$C_n=2(n+1)H_n-\frac{8}{3}n-\frac{2}{3},n>1\tag{2.14}$$ 和之前一样，可以验证小的情况 $$H_2=3/2,C_2=3$$ $$H_3=11/6,C_3=6$$