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

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

和式和递归式

和式 \(\to\) 递归式

和式 \[ S_n=\sum_{k=0}^na_k \] 等价于递归式 \[ \begin{cases}S_0=0\\S_n=S_{n-1}+a_n\end{cases} \] 于是我们可以用第一章中解递归式的方法（成套方法）解出和式。

递归式 \(\to\) 和式

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

设有递归式： \[ a_nT_n=b_nT_{n-1}+c_n \] 我们用一个求和因子（summation factor）\(s_n\) 乘两边，其中 \(s_n\) 满足：\(s_nb_n=s_{n-1}a_{n-1}\)，得到： \[ s_na_nT_n=s_nb_nT_{n-1}+s_nc_n=s_{n-1}a_{n-1}T_{n-1}+s_nc_n \] 解得： \[ s_na_nT_n=s_0a_0T_0+\sum_{i=1}^ns_ic_i=s_1b_1T_0+\sum_{i=1}^ns_ic_i \] 故 \[ T_n=\frac{1}{s_na_n}\left(s_1b_1T_0+\sum_{i=1}^ns_ic_i\right) \] 现在关键在于求 \(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}b_2}s_1 \] 其中 \(s_1\) 任取一个常数（比如 \(1\)）即可。

例子

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

• 解快速排序中出现的递归式：典型的快速排序算法所做的比较步骤的平均次数满足递归式： \[ \begin{cases}C_0=C_1=0\\C_n=n+1+\frac{2}{n}\sum\limits_{k=0}^{n-1}C_k\end{cases} \] 这个 \(C_n\) 依赖于前 \(n-1\) 项，我们先简化一下：两边同乘 \(n\)，列出 \(C_n\) 和 \(C_{n-1}\) 的递归式： \[ \begin{cases} nC_n=n^2+n+2\sum\limits_{k=0}^{n-1}C_k\\ (n-1)C_{n-1}=(n-1)^2+n-1+2\sum\limits_{k=0}^{n-2}C_k \end{cases} \] 两式相减，化简得到： \[ nC_n=(n+1)C_{n-1}+2n \] 这个我们高中也会做，同除 \(\frac{1}{n(n+1)}\) 就好。现在我们算求和因子：\(s_n=\frac{(n-1)\cdots 2\cdot1}{(n+1)n\cdots3}=\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} \]

和式的处理

我们可以对和式的下标进行灵活的变换： \[ \sum_{k\in K}a_k=\sum_{p(k)\in K}a_{p(k)} \] 更普通的写法： \[ \sum_{j\in J}a_{f(j)}=\sum_{k\in K}a_k\#f^-(k) \] 其中，#\(f^-(k)\) 表示集合 \(f^-(k)=\{j\mid f(j)=k\}\) 中元素的个数。

扰动法（\(\text{perturbation method}\)）：计算和式 \(S_n=\sum\limits_{k=0}^na_k\) 可以这么做： \[ S_{n+1}=S_n+a_{n+1}=a_0+\sum_{k=0}^na_{k+1} \] 左式是抽出最后一项，右式是抽出第一项，然后试着把 \(\sum\limits_{k=0}^na_{k+1}\) 写成 \(S_n\) 的函数，这样我们就有了一个关于 \(S_n\) 的方程，解出来就可以了。

例如：求解 \(S_n=\sum\limits_{k=0}^nk2^k\)，用扰动法： \[ S_n+(n+1)2^{n+1}=\sum\limits_{k=0}^n(k+1)2^{k+1}=2\sum\limits_{k=0}^nk2^k+\sum\limits_{k=0}^n2^{k+1}=2S_n+2^{n+2}-2 \] 解得：\(S_n=(n+1)2^{n+1}-2^{n+2}+2=(n-1)2^{n+1}+2\).

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

多重和式

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

简易型

\(j,k\) 的范围相互无关： \[ \sum_{j\in J}\sum_{k\in K}a_{j,k}=\sum_{k\in K}\sum_{j\in J}a_{j,k} \] 特别地，有一般分配律： \[ \sum_{j\in J}\sum_{k\in K}a_jb_k=\left(\sum_{j\in J}a_j\right)\left(\sum_{k\in K}b_k\right) \]

复杂型

\(j,k\) 的范围相关： \[ \sum_{j\in J}\sum_{k\in K(j)}a_{j,k}=\sum_{k\in K'}\sum_{j\in J'(k)}a_{j,k} \] 换序时保证两式的范围相同即可，即保证：\([j\in J][k\in K(j)]=[k\in K'][j\in J'(k)]\).

比如说， \[ \sum_{j=1}^n\sum_{k=j}^na_{j,k}=\sum_{1\leqslant j\leqslant k\leqslant n}a_{j,k}=\sum_{k=1}^n\sum_{j=1}^ka_{j,k} \] 可以理解成 \(x\) 型区域和 \(y\) 型区域的两种表示。

再比如说，做莫比乌斯反演的题的时候经常要用： \[ \sum_{i=1}^n\sum_{d\mid i}f(d,i)=\sum_{d=1}^n\sum_{i=1}^n[d\mid i]f(d,i)=\sum_{d=1}^n\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}f(d,di) \] 或者说： \[ \sum_{i=1}^n\sum_{j=1}^m\sum_{d\mid \gcd(i,j)}f(d,i,j)=\sum_{d=1}^{\min(n,m)}\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}f(d,di,dj) \] 也是如此。

一个有趣的例子

计算 \[ S_n=\sum_{1\leqslant j<k\leqslant n}\frac{1}{k-j} \] 第一次尝试：（先对 \(j\) 求和，再对 \(k\) 求和） \[ \begin{align} S_n=\sum_{k=1}^n\sum_{j=1}^k\frac{1}{k-j}&=\sum_{k=1}^n\sum_{j=1}^{k-1}\frac{1}{j}&&用\;k-j\;代替\;j\\ &=\sum_{k=1}^nH_{k-1}&&调和数的定义\\ &=\sum_{k=0}^{n-1}H_k \end{align} \] 没法进行了。

第二次尝试：（先对 \(k\) 求和，再对 \(j\) 求和） \[ \begin{align} S_n=\sum_{j=1}^n\sum_{k=j+1}^n\frac{1}{k-j}&=\sum_{j=1}^n\sum_{k=1}^{n-j}\frac{1}{k}&&用\;k+j\;替换\;k\\ &=\sum_{j=1}^nH_{n-j}&&调和数的定义\\ &=\sum_{j=0}^{n-1}H_j&&用\;n-j\;替换\;j \end{align} \] 和第一次尝试结果一样。

第三次尝试：（先代换） \[ \begin{align} S_n=\sum_{1\leqslant j<k\leqslant n}\frac{1}{k-j}&=\sum_{1\leqslant j<u+j\leqslant n}\frac{1}{u}&&令\;u=k-j\\ &=\sum_{j=1}^{n}\sum_{u=1}^{n-j}\frac{1}{u}\\ &=\sum_{u=1}^{n}\sum_{j=1}^{n-u}\frac{1}{u}&&求和号换序\\ &=\sum_{u=1}^{n}\left(\frac{n}{u}-1\right)\\ &=nH_n-n \end{align} \] 搞定。

上述尝试还给了我们一个恒等式： \[ \sum_{k=0}^{n-1}H_k=nH_n-n \]

一般性方法

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

以求解 \[ \square_n=\sum_{k=0}^nk^2 \] 的封闭形式为例，探究至少 \(8\) 种解决问题的方法。

方法0：查找公式

作为 OIer/ACMer，我们都会一个方法：算出前几项，然后愉快地 \(\text{OEIS}\). 链接

练习：在毕导的视频中，男厕尴尬定理的递归式长这样：\(\begin{cases}f(1)=f(2)=1\\f(3)=2\\f(2n+1)=2f(n+1)-1\\f(2n)=f(n)+f(n+1)-1\end{cases}\)，我们可以打表找规律求解（毕导也是这么做的），这个规律还是比较好找的。如果我们试着 \(\text{OEIS}\)，输入 \(1,1,2,2,3,3,3,4,5,5,5,5,5\)，就会发现，早有人给出了这个问题以及解，只不过他没有以厕所而是电话亭举例。

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

假设我们现在神奇地知道了 \(\square_n=\frac{n\left(n+\frac{1}{2}\right)(n+1)}{3}\)，于是归纳证明：

• 对于 \(n=0\)，有 \(\square_0=0=\frac{0\left(0+\frac{1}{2}\right)(0+1)}{3}\)，成立；
• 假设 \(n-1\) 成立，则 \(3\square_n=3\square_{n-1}+3n^2=(n-1)\left(n-\frac{1}{2}\right)n+3n^2=n\left(n+\frac{1}{2}\right)(n+1)\)，成立。证毕。

方法2：对和式用扰动法

抽出最后一项和第一项： \[ \begin{align} \square_{n+1}&=\square_{n}+(n+1)^2\\ &=\sum_{k=1}^{n+1}k^2=\sum_{k=0}^n(k+1)^2=\sum_{k=0}^nk^2+\sum_{k=0}^n2k+\sum_{k=0}^n1\\ &=\square_n+2\sum_{k=0}^nk+n+1 \end{align} \] 完蛋，\(\square_n\) 被约掉了！但是！注意它给出了 \(\sum\limits_{k=0}^nk\) 的封闭形式，所以不妨“升维打击”一波（设 \(\triangle_n=\sum\limits_{k=0}^nk^3\)）： \[ \begin{align} \triangle_{n+1}&=\triangle_n+(n+1)^3\\ &=\sum_{k=1}^{n+1}k^3=\sum_{k=0}^n(k+1)^3=\sum_{k=0}^n(k^3+3k^2+3k+1)\\ &=\triangle_n+3\square_n+3\cdot\frac{n(n+1)}{2}+n+1 \end{align} \] 耶！解得：\(\square_n=\frac{n\left(n+\frac{1}{2}\right)(n+1)}{3}\).

方法3：建立成套方法

设有递归式： \[ \begin{cases}R_0=\alpha\\R_n=R_{n-1}+\beta+\gamma n+\delta n^2\end{cases} \] 它有解：\(R_n=A(n)\alpha+B(n)\beta+C(n)\gamma+D(n)\delta\).

当 \(\delta=0\) 时，问题转化成我们已经解决过的问题，所以 \(A(n),B(n),C(n)\) 已经搞定了；

然后设 \(R_n=n^3\)，解得：\((\alpha,\beta,\gamma,\delta)=(0,1,-3,3)\)，得到：\(B(n)-3C(n)+3D(n)=n^3\)，于是 \(D(n)\) 也搞定了。

由于 \(\square_n=\square_{n-1}+n^2\)，我们只需要设 \((\alpha,\beta,\gamma,\delta)=(0,0,0,1)\)，那么 \(R_n=D(n)=\square_n\).

练习：求 \(\sum\limits_{k=0}^n(-1)^kk^2\) 的封闭形式。

解：有递归式：\(\begin{cases}R_0=\alpha\\R_n=R_{n-1}+(-1)^n(\beta+\gamma n+\delta n^2)\end{cases}\)，设解为 \(R_n=A(n)\alpha+B(n)\beta+C(n)\gamma+D(n)\delta\)，需要找到四个特解：

• 令 \(R_n=1\)，解得：\((\alpha,\beta,\gamma,\delta)=(1,0,0,0)\)，得到：\(A(n)=1\)；
• 令 \(R_n=(-1)^n\)，解得：\((\alpha,\beta,\gamma,\delta)=(1,2,0,0)\)，得到：\(A(n)+B(n)=(-1)^n\)；
• 令 \(R_n=(-1)^nn\)，解得：\((\alpha,\beta,\gamma,\delta)=(0,-1,2,0)\)，得到：\(-B(n)+2C(n)=(-1)^nn\)；
• 令 \(R_n=(-1)^nn^2\)，解得：\((\alpha,\beta,\gamma,\delta)=(0,1,-2,2)\)，得到：\(B(n)-2C(n)+2D(n)=(-1)^nn^2\).

我们只需要设 \((\alpha,\beta,\gamma,\delta)=(0,0,0,1)\)，就知道了：\(原式=D(n)=\frac{(-1)^n}{2}(n^2+n)\).

方法4：积分代替和式

由于 \(\int_0^nx^2\mathrm dx=\frac{n^3}{3}\)，所以我们有近似：\(\square_n\sim\frac{n^3}{3}\).

然后我们来对误差进行精确分析：设误差 \(E_n=\square_n-\frac{n^3}{3}\)，由于 \(\square_n=\square_{n-1}+n^2\)，所以我们有： \[ E_n=E_{n-1}+n-\frac{1}{3} \] 这个递归式很好解，解出来就行了。

方法5：展开和收缩

大致思路：一重和式 \(\to\) 二重和式 \(\to\) 封闭形式。 \[ \begin{align} \square_n&=\sum_{k=1}^nk^2=1+(2+2)+(3+3+3)+\cdots+(n+n+\cdots+n)=\sum_{k=1}^n\sum_{j=1}^kk\\ &=\sum_{j=1}^n\sum_{k=j}^nk=\sum_{j=1}^n\frac{(j+n)(n-j+1)}{2}\\ &=\frac{1}{2}\sum_{j=1}^n\left(n(n+1)+j-j^2\right)\\ &=\frac{1}{2}n^2(n+1)+\frac{1}{4}n(n+1)-\frac{1}{2}\square_n \end{align} \] 解出来即可。

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

练习：求 \(\triangle_n=\sum\limits_{k=1}^nk^3\) 的封闭形式。

解： \[ \begin{align} \triangle_n&=\sum_{k=1}^nk^3=\sum_{k=1}^n\sum_{j=1}^kk^2=\sum_{j=1}^n\sum_{k=j}^nk^2=\sum_{j=1}^n(\square_n-\square_{j-1})\\&=\sum_{j=1}^n\left(\frac{n(n+1)(2n+1)}{6}-\frac{(j-1)j(2j-1)}{6}\right)\\&=\frac{n^2(n+1)(2n+1)}{6}-\frac{1}{6}\sum_{j=1}^n(2j^3-3j^2+j)\\&=\frac{n^2(n+1)(2n+1)}{6}-\frac{1}{3}\triangle_n+\frac{n(n+1)(2n+1)}{12}-\frac{n(n+1)}{12} \end{align} \] 解得：\(\triangle_n=\frac{n^2(n+1)^2}{4}\).

方法6：有限微积分

见第二部分

方法7：生成函数

见之后的章节

无限和式

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