[具体数学]第二章·和式（第一部分）

第二章·和式分7节，这是我的笔记第一部分，包括：和式与递归式的联系，和式和多重和式的处理方法，无限和式。

和式和递归式

和式 $\to$ 递归式

和式 $$S_n=\sum _{k=0}^n{a}_k$$ 等价于递归式 $$\{\begin{array}{l}{S}_0=0\\ S_n=S_{n-1}+a_n\end{array}$$ 于是我们可以用第一章中解递归式的方法（成套方法）解出和式。

递归式 $\to$ 和式

通过求出和式解递归式，这个实用多了。

设有递归式： $$a_n{T}_n=b_n{T}_{n-1}+c_n$$ 我们用一个求和因子（summation factor）$s_n$ 乘两边，其中 $s_n$ 满足：$s_n{b}_n=s_{n-1}{a}_{n-1}$，得到： $$s_n{a}_n{T}_n=s_n{b}_n{T}_{n-1}+s_n{c}_n=s_{n-1}{a}_{n-1}{T}_{n-1}+s_n{c}_n$$ 解得： $$s_n{a}_n{T}_n=s_0{a}_0{T}_0+\sum _{i=1}^n{s}_i{c}_i=s_1{b}_1{T}_0+\sum _{i=1}^n{s}_i{c}_i$$ 故 $$T_n=\frac{1}{s_n{a}_n}(s_1{b}_1{T}_0+\sum _{i=1}^n{s}_i{c}_i)$$ 现在关键在于求 $s_n$，由于 $s_n{b}_n=s_{n-1}{a}_{n-1}$，所以我们不难知道： $$s_n=\frac{a_{n-1}{a}_{n-2}\cdots a_1}{b_n{b}_{n-1}{b}_2}{s}_1$$ 其中 $s_1$ 任取一个常数（比如 $1$）即可。

例子

• 解 $\mathbf{\text{Hanoi}}$ 塔递归式： $$\{\begin{array}{l}{T}_0=0\\ T_n=2T_{n-1}+1\end{array}$$ 这个我们高中就会做，两边 $+1$ 就变成了等比数列，或者两边除以 $2^n$ 就变成了等差数列。后者其实就是求和因子的做法（$s_n=\frac{1}{2^n}$）。

• 解快速排序中出现的递归式：典型的快速排序算法所做的比较步骤的平均次数满足递归式： $$\{\begin{array}{l}{C}_0=C_1=0\\ C_n=n+1+\frac{2}{n}\sum _{k=0}^{n-1}{C}_k\end{array}$$ 这个 $C_n$ 依赖于前 $n-1$ 项，我们先简化一下：两边同乘 $n$，列出 $C_n$ 和 $C_{n-1}$ 的递归式： $$\{\begin{array}{l}n{C}_n=n^2+n+2\sum _{k=0}^{n-1}{C}_k\\ (n-1)C_{n-1}=(n-1{)}^2+n-1+2\sum _{k=0}^{n-2}{C}_k\end{array}$$ 两式相减，化简得到： $$n{C}_n=(n+1)C_{n-1}+2n$$ 这个我们高中也会做，同除 $\frac{1}{n(n+1)}$ 就好。现在我们算求和因子：$s_n=\frac{(n-1)\cdots 2\cdot 1}{(n+1)n\cdots 3}=\frac{2}{n(n+1)}$ 也验证了这个做法。

  最后解出来是： $$C_n=2(n+1)\sum _{k=1}^n\frac{1}{k+1}-\frac{2}{3}(n+1)=2(n+1)H_n-\frac{8}{3}n-\frac{2}{3}$$

和式的处理

我们可以对和式的下标进行灵活的变换： $$ 更普通的写法： $$ 其中，#$$ 表示集合 $$ 中元素的个数。

扰动法（$$）：计算和式 $$ 可以这么做： $$ 左式是抽出最后一项，右式是抽出第一项，然后试着把 $$ 写成 $$ 的函数，这样我们就有了一个关于 $$ 的方程，解出来就可以了。

例如：求解 $$，用扰动法： $$ 解得：$$.

当然，这玩意儿也可以求导做，变成无穷级数的话就是个很常规的高数题。

多重和式

主要就是求和号换序的问题。

简易型

$$ 的范围相互无关： $$ 特别地，有一般分配律： $$

复杂型

$$ 的范围相关： $$ 换序时保证两式的范围相同即可，即保证：$$.

比如说， $$ 可以理解成 $$ 型区域和 $$ 型区域的两种表示。

再比如说，做莫比乌斯反演的题的时候经常要用： $$ 或者说： $$ 也是如此。

一个有趣的例子

计算 $$ 第一次尝试：（先对 $$ 求和，再对 $$ 求和） $$ 没法进行了。

第二次尝试：（先对 $$ 求和，再对 $$ 求和） $$ 和第一次尝试结果一样。

第三次尝试：（先代换） $$ 搞定。

上述尝试还给了我们一个恒等式： $$

一般性方法

这一节算是一个小总结吧。

以求解 $$ 的封闭形式为例，探究至少 $$ 种解决问题的方法。

方法0：查找公式

作为 OIer/ACMer，我们都会一个方法：算出前几项，然后愉快地 $$. 链接

练习：在毕导的视频中，男厕尴尬定理的递归式长这样：$$，我们可以打表找规律求解（毕导也是这么做的），这个规律还是比较好找的。如果我们试着 $$，输入 $$，就会发现，早有人给出了这个问题以及解，只不过他没有以厕所而是电话亭举例。

方法1：猜测答案+归纳证明

假设我们现在神奇地知道了 $$，于是归纳证明：

• 对于 $$，有 $$，成立；
• 假设 $$ 成立，则 $$，成立。证毕。

方法2：对和式用扰动法

抽出最后一项和第一项： $$ 完蛋，$$ 被约掉了！但是！注意它给出了 $$ 的封闭形式，所以不妨“升维打击”一波（设 $$）： $$ 耶！解得：$$.

方法3：建立成套方法

设有递归式： $$ 它有解：$$.

当 $$ 时，问题转化成我们已经解决过的问题，所以 $$ 已经搞定了；

然后设 $$，解得：$$，得到：$$，于是 $$ 也搞定了。

由于 $$，我们只需要设 $$，那么 $$.

练习：求 $$ 的封闭形式。

解：有递归式：$$，设解为 $$，需要找到四个特解：

• 令 $$，解得：$$，得到：$$；
• 令 $$，解得：$$，得到：$$；
• 令 $$，解得：$$，得到：$$；
• 令 $$，解得：$$，得到：$$.

我们只需要设 $$，就知道了：$$.

方法4：积分代替和式

由于 $$，所以我们有近似：$$.

然后我们来对误差进行精确分析：设误差 $$，由于 $$，所以我们有： $$ 这个递归式很好解，解出来就行了。

方法5：展开和收缩

大致思路：一重和式 $$ 二重和式 $$ 封闭形式。 $$ 解出来即可。

你以为它变麻烦了，实际上它变简单了……

练习：求 $$ 的封闭形式。

解： $$ 解得：$$.

方法6：有限微积分

见第二部分

方法7：生成函数

见之后的章节

无限和式

其实就是无穷级数，高数都学过，略去。