持续更新ing
第2章 和式
2.1 记号
- 艾弗森括号
若 $P(k)$ 为真，则$[P(k)] = 1$；若 $P(k)$ 为假，则 $[P(k)] = 0 $ .
特别的，我们约定，当 $P(k)$ 为假时，式子 $a_k [P(k)] $ 一定为 $0$ ，即使 $ a_k$ 无定义.
2.2 和式与递归式
- 求和因子法
Q2-1： 将递归式 $a_n T_n = b_n T_{n-1} + c_n$ 化为和式.
解：设 $s_n$ 满足
$s_n b_n = s_{n-1} a_{n-1}$
对 $s_n b_n = s_{n-1} a_{n-1}$ 累乘可得
$ s_n = \frac{\prod_{k=1}^{n-1}a_k}{\prod_{k=2}^nb_k}\\ $
在原式两边同乘 $s_n$ 有
$s_n a_n T_n =s_n b_n T_{n-1} +s_n c_n$
记 $S_n=s_n a_n T_n$，由以上两式，可得
$S_n =S_{n-1}+s_n c_n$
从而
$S_n = s_1 b_1 T_0 + \sum_{k=1}^ns_kc_k $
所以原递归式解为
$T_n = \frac1{s_na_n}\ (s_1 b_1 T_0 + \sum_{k=1}^ns_kc_k) $
Q2-2：典型的快速排序算法所做的比较步骤平均次数满足递归式
$C_0 = C_1 = 0$
$C_n = n+1+\frac2n\sum_{k=0}^{n-1}C_k\ ,n>1$
请将其化为和式.
解：原式两边同时乘以 $n$ ，得
$n C_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$
两式相减，得
$n C_n – (n-1) C_{n-1} = 2n + 2 C_{k-1} ,n > 2$
所以原递归式可化简为
$C_0 = C_1 =0;C_2=3$
$n C_n = (n+1) C_{k-1} +2n ,n > 2$
根据 Q1 中的一般结论，有
$a_n = n,b_n=n+1,c_n=2n-2[n=1]+2[n=2]$
$ s_n = \frac2{n(n+1)}\\ $
所以，原递归式的解为
$ C_n = 2(n+1) \sum_{k=1}^n\frac1{k+1} – \frac23 (n+1) $
化简后为
$ C_n = 2(n+1)H_n -\frac83 n – \frac23\\ $
2.3 和式的处理
- 扰动法
Q2.3： 求解和式 $ S_n = \sum_{k=0}^nkx^k $.
解：原式可化为
$S_n+(n+1)x^{n+1} = \sum_{k=0}^n(k+1)x^{k+1} $
将右式拆开，得
$S_n+(n+1)x^{n+1} = \sum_{k=0}^nkx^{k+1} + \sum_{k=0}^nx^{k+1} $
右式的两部分，一个等于 $ xS_n $ ，另一个和式是个几何级数，带入计算，得
$S_n = \frac{x-(n+1)x^{n+1}+nx^{n+2}}{{(1-x)}^2} $
2.4 多重和式
- 交换求和次序基本法则
$ \sum_{j}\sum_{k} a_{j,k}[P(j,k)] = \sum_{P(j,k)} a_{j,k} = \sum_{k}\sum_{j} a_{j,k}[P(j,k)] $
- 一般分配律
$\sum_{j\in J,k\in K}a_jb_k = (\sum_{j\in J}a_j)(\sum_{k\in K}b_k) $
Q2.4： 求解和式 $ S=\sum_{1\leqslant j\leqslant k\leqslant n} a_j a_k $.
解：因为 $ a_j a_k = a_k a_j $ ，所以我们可以交换求和次序
$ S=\sum_{1\leqslant j\leqslant k\leqslant n} a_j a_k = \sum_{1\leqslant k\leqslant j\leqslant n} a_j a_k =S^’$
两式相加，有
$ 2S = S+S’ = \sum_{1\leqslant j,k\leqslant n} a_j a_k + \sum_{1\leqslant k=j\leqslant n} a_j a_k$
根据一般分配律，上面的第一个式子等于 $ (\sum_{1\leqslant k\leqslant n}a_k)^2$ ，所以我们有
$ S = \frac12 ( (\sum_{k=1}^na_k)^2 + \sum_{k=1}^na_k^2)$
Q2.5 ：求解和式 $ S=\sum_{1\leqslant j<k\leqslant n}(a_j-a_k)(b_j-b_k)$.
解：交换 $j,k$ 得
$ S=\sum_{1\leqslant k<j\leqslant n}(a_j-a_k)(b_j-b_k) = \sum_{1\leqslant k<j\leqslant n}(a_k-a_j)(b_k-b_j)$
利用 $[1 \leq j < k \leq n] + [1 \leq k < j \leq n] = [1 \leq k,q \leq n] – [1 \leq k = q \leq n]$,将 $S$ 与自身相加得
$ 2S = \sum_{1\leqslant k,j \leqslant n}(a_j-a_k)(b_j-b_k) – \sum_{1\leqslant k=j\leqslant n}(a_j-a_k)(b_j-b_k)$
展开，得
$ S = \sum_{1\leqslant k,j \leqslant n}a_{k}b_{k} – \sum_{1\leqslant k,j \leqslant n}a_{j}b_{k}$
即
$ \sum_{1\leqslant j<k\leqslant n}(a_j-a_k)(b_j-b_k) = n\sum_{k=1}^na_kb_k- (\sum_{k=1}^na_k)(\sum_{k=1}^nb_k)$
Tips:该式是切比雪夫单调不等式的一个特例：
$ (\sum_{k=1}^na_k)(\sum_{k=1}^nb_k) \leq n\sum_{k=1}^na_kb_k, a_1 \leq … \leq a_n 且 b_1 \leq … \leq b_n$
$ (\sum_{k=1}^na_k)(\sum_{k=1}^nb_k) \geq n\sum_{k=1}^na_kb_k, a_1 \leq … \leq a_n 且 b_1 \geq … \geq b_n$
Q2.6： 求解和式 $ S_n =\sum_{1\leqslant j<k\leqslant n} \frac1{k-j}$.
解：$S_n = \sum_{k=1}^n \sum_{j=1}^{k-1} \frac1 {k-j}$
$ \; \; \; \;\; \;= \sum_{k=1}^n \sum_{1 \leq k-j < k} \frac1 {j}$
$ \; \; \; \;\; \;= \sum_{k=1}^n \sum_{0 < j \leq k-1} \frac1 {j}$
$ \; \; \; \;\; \;= \sum_{k=1}^n H_{k-1}$
$ \; \; \; \; \; \;= \sum_{k=0}^{n-1} H_{k}$
如果在开始用 $k+j$ 替换 $k$ 则有
$ S_n =\sum_{1\leqslant j<k+j \leqslant n} \frac1{k}$
$ \; \; \; \;\; \;= \sum_{1 \leq k \leq n} \frac {n-k} k$
$ \; \; \; \;\; \;= nH_n + n$
所以我们得到一个恒等式
$\sum_{k=0}^{n-1} H_{k} = nH_n + n $