求和因子
在第一章中，我们对于递归式
使用了两边 \(+1\) 然后转化为 \(U_n\) 的方法，从而得出 \(T_n = 2^n - 1\)。
我们还可以采用另外一种方法。令两边除以 \(2^n\)，
再令 \(S_n = \dfrac{T_n}{2^n}\)，那么 \(S_n = S_{n-1} + \dfrac{1}{2^n}\)，且 \(S_0 = 0\)。于是，根据几何级数求和的技巧，我们得到 \(S_n = 1 - \dfrac{1}{2^n}\)，从而 \(T_n = 2^n - 1\)。
一般地，对于形如
的递归式，如果能够找到一个求和因子（summation factor）\(s_n\) 来乘等式两边，
将成立。如果我们有 \(s_nb_n = s_{n-1}a_{n-1} (n>1)\)，那么令 \(S_n = s_na_n T_n\)，我们就有
事实上，要令 \(s_nb_n = s_{n-1}a_{n-1}\)，那么就要让 \(s_n= \dfrac{a_{n-1}}{b_{n}}s_{n-1}\)。我们不断展开这个等式，最终在 \(s_1\) 处停止（对于求和因子选取的限制只在 \(n > 1\) 时生效）。可以得到 \(s_n = \dfrac{a_{n-1}a_{n-2}\cdots a_{a_1}}{b_nb_{n-1}\cdots b_{2}}s_1\)。\(s_1\) 可以选取任意常数，因此前面的分式 \(\dfrac{a_{n-1}a_{n-2}\cdots a_{1}}{b_nb_{n-1}\cdots b_{2}}\) 的任意常数倍，会是一个合法的求和因子。
例
求解
\[C_0 = C_1 = 0, \\ C_n = n+1 + \frac{2}{n}\sum \limits_{i=0}^{n-1} C_i \ \ (n>1) \]
为了求解，我们首先避免除法
然后用 \(n-1\) 代替 \(n\)，尝试消掉后面和式中的某些部分
于是我们有
看上去我们只能对后面 \(n>2\) 的部分使用求和因子法，此时有 \(a_n = n,b_n = n+1, c_n = 2n\)。不过如果你的注意力比较集中，那么我们便可以在 \(c_n = 2n\) 的基础上，对其进行一些小小的修改，例如令 \(c_n = 2n-2[n=1]+2[n=2]\)，这样 \(a_nC_n = b_nC_{n-1} + c_n\) 对于任何 \(n > 0\) 都将成立。
这样，我们便可以选取合适的求和因子了。
在 \(n \geq 3\) 时显然是成立的。在 \(n = 2\) 时，经过验证，它也是成立的。因此，\(s_n = \dfrac{2}{(n+1)n}\) 是一个合适的求和因子。
这时我们就有
这样我们的推导便差不多完成了。
调和数：\(H_n = \sum \limits_{i=1}^{n} \dfrac{1}{i}\)。对于上面的 \(\sum \limits_{i=1}^{n} \dfrac{1}{i+1}\)，它显然等于 \(H_{n+1} - 1\)，也即 \(H_n - \dfrac{n}{n+1}\)。于是，我们有
和式的处理技巧 · 扰动法
对于一个未知的和式
我们可以将它加上一项 \(a_{n+1}\)，然后把第 \(0\) 项分离出来，
如果我们能够使用一些手段把后面的和式表示为和 \(S_n\) 相关形式，那么我们就得到了关于 \(S_n\) 的一个方程，从而可以解出 \(S_n\)。
以几何级数 \(S_n = \sum \limits_{0 \leq i \leq n} ax^i\) 为例：
以 \(S_n = \sum \limits_{0 \leq i \leq n} i2^i\) 为例：
后面便是我们刚才算出的几何级数。这样，我们便有
对于 \(S_n=\sum\limits_{0 \leq i \leq n}ix^i\) 我们可以得到类似的结论。
下面是书上 P37 的一个更具有挑战性的例子。对于 \(S_n = \sum \limits_{0 \leq i \leq n} i^2\)，我们尝试对其使用扰动法
我们已经足以想象糟糕的结果：\(S_n\) 被左右抵消了：
不过我们获得了安慰奖：前 \(n+1\) 个非负整数的平方和。
聪明的你可能会发现，如果我们要导出平方和的封闭形式，我们也许需要的不是扰动它自己，而是对立方和进行扰动！让我们试试。这次令 \(S_n = \sum \limits_{0 \leq i \leq n} i^3\)，
便得到了喜闻乐见的平方和公式。
多重和式的处理技巧
对于形如
的简单型和式，容易观察到 \(J\) 和 \(K\) 相互无关，于是我们可以改变求和顺序
但是，对于内外求和下标有关的复杂型和式，情况就变得不同了。
要成立，则需要满足
以下是一些例子。
对于多重和式，我们一般希望将其化作几个单重和式，并分别计算结果。这通常比直接计算多重和式的值要简单。以下是一个例子：对于和式
利用恒等式
可以得到
\(S\) 的值显而易见。
书上 P32 指出，如果调换最终等式的顺序，我们可以得到
最后一个和式就是 \(S\)。这样就导出切比雪夫单调不等式 (Chebyshev's monotonic inequality) 的和式情形：
对于另一个和式
我们通过平凡的推导可以得到，
最终得到了一个调和数求和的和式。但是如果我们采用另外一种推导的方式，
从第一行到第二行的推导是关键的。我们为了让求和下标尽可能不相互影响，用 \(j+k\) 替换了 \(k\)，从而得到了第二行的结果。我们顺便得到了 \(\sum \limits_{1 \leq k < n} H_k = nH_n - n\)。
P34 提到，如果我们有一个包含 \(k + f(j)\) 的二重和式，那么可以先做 \(k \leftarrow k - f(j)\) 的变量替换，这样会使得求和的对象不同时和 \(j,k\) 相关，然后再按照外层 \(k\)，内层 \(j\) 的顺序求和。
和式的处理技巧 · 积分模拟
求和 \(S_n = \sum \limits_{0 \leq k \leq n} f(i)\) 和积分 \(I_n = \int_{0}^{n} f(x)\text{d}x\) 是比较相似的，只不过它们存在误差项。如果 \(E_n = \sum \limits_{0 \leq k \leq n} (f(k) - \int_{k-1}^{k} f(x) \text{d}x)\) 好求，那么我们便可以算出 \(I_n,E_n\)，并利用 \(S_n = I_n + E_n\) 来计算出 \(S_n\)。
对于 \(f(x) = x^2\)，我们有
有限微积分和无限微积分
算子 (operator) 作用在函数上并给出新的函数。与微分算子 \(\text D f(x) = \lim \limits_{h \rightarrow 0} \frac{f(x+h)-f(x)}{h}\) 类似地定义向前差分算子：\(\Delta f(x) = f(x+1)-f(x)\)。
我们仿照普通微积分来定义有限微积分。我们知道幂函数的微分：\(f(x) = x^m \Rightarrow \text{D}f(x) = mx^{m-1}\)。如果我们对于 \(m \geq 0\)，定义下降幂
那么对于 \(m \geq 1\)，\(f(x) = x^{\underline m}\)，就有 \(\Delta f(x) = mx^{\underline{m-1}}\)。
现在是时候考虑积分了。微分算子 \(\text D\) 的逆运算，积分算子 \(\int\) 的关系是：
其中 \(C\) 为常函数。类似地，我们有差分算子 \(\Delta\) 的逆运算求和算子 \(\sum\)，它们的关系是：
与不定积分不同，这里的 \(C\) 不需要满足它是常函数，只需要对于任意整数 \(x\) 有 \(C(x) = C(x-1)\) 就可以了。究其原因是无限微积分的 \(h \to 0\)，而有限微积分的 \(h = 1\)，因此尽管我们努力地模仿了无限微积分，但是偶尔还是会得出不一样的结果。
与定积分类似地，我们定义和式，使得
通过 P41 的推导我们直接得到
这样我们就有 \(\sum \nolimits_{a}^{b} g(x) \delta x + \sum \nolimits_{b}^{c} g(x) \delta x = \sum \nolimits_{a}^{c} g(x) \delta x\)，对于所有整数 \(a,b,c\) 成立。
对于下降幂 \(x^{\underline{-m}}\)，在 \(m\) 为正整数的时候我们可以做出类似的定义，并且使得性质 \(x^{\underline{m}}(x-m)^{\underline n} = x^{\underline{m+n}}\) 对于任意整数 \(m,n\) 成立：
从而我们有
而在 \(m=-1\) 时有
其中 \(H\) 是调和数。不难发现这对应了无限微积分中 \(\frac{1}{x}\) 的积分 \(\ln x+C\)，于是我们说 \(H\) 是 \(\ln\) 的一个有限模拟。
本节剩下的部分，书上给出了一些常见函数的差分表和逆差分（和式）表。
另外，因为在差分中 \(h \to 1\)，所以 \(\Delta(f(x+1)) = (\Delta f)(x+1)\) 是成立的，将 \(1\) 替换为任意常整数 \(c\) 亦然。
剩下的部分中有一个重点：\(u(x)v(x)\) 的差分。
其中 \(\text E\) 是移位算子，\(\text{E}f(x) = f(x+1)\)。
事实上，\(u(x)v(x)\) 的地位应该是平等的，因此我们有
最后，来考虑微积分中的 \(u(x)v(x)\) 求导法则
导出分部积分法则。
于是有分部求和法则
我们要求 \(\sum uv\) 时，如果直接求不好求，可以把 \(v\) 表示成某个函数 \(v'\) 的差分，然后求解。
理性愉悦：无限和式
对于无限集合 \(K\)，满足任意 \(k \in K\) 都有 \(a_k\) 非负，如果对于任意有限子集 \(F \subseteq K\)，都有
那么符合条件的最小的 \(A\) 就是这个无限和式的值，否则说这个和式的值为 \(\infty\)。如果 \(K\) 取非负整数集合，等价的定义是
如果集合中有负数，我们需要分开考虑。对于 \(K = P \cup M\)，其中 \(k \in P\) 有 \(a_k \geq 0\)，\(k \in M\) 有 \(a_k < 0\)，那么只有
都不为 \(\infty\)，我们才定义 \(\sum \limits_{k \in K} a_k=\sum \limits_{k \in P} a_k -\sum \limits_{k \in M} -a_k\)，称其绝对收敛于 \(\sum \limits_{k \in P} a_k -\sum \limits_{k \in M} -a_k\)。
类似地，对于任意复数集 \(K\)，我们可以把集合分成虚、实两个部分，对于每个部分分成正、负两个部分，然后分别求和，从而定义和式的值。
接下来，我们需要证明一个重要的定理：如果一个复数组成的和式是绝对收敛的，那么可以以任意顺序将这个和式求和。换句话说，如果
那么对于任意 \(j \in J\) 存在复数 \(A_j\) 使得
成立。我们只证明 \(a_{j,k}\) 为非负实数的情形。
首先注意到，\(\sum \limits_{k \in K_j} a_{j,k}\) 对于所有 \(j \in J\) 都是绝对收敛的，因为 \(K_j\) 的所有有限子集 \(F_j\) 显然是 \(A\) 的一个有限子集。因为整个和式绝对收敛于 \(A\)，所以它绝对收敛。
其次，让我们证明，\(\sum \limits_{j \in J} A_{j}\) 绝对收敛，且 \(A\) 是最小的上界。最精妙的一步来了：如果存在 \(J\) 的有限子集 \(G\) 使得 \(\sum \limits_{j \in G} A_j = A' > A\)，那么我们可以对于每个 \(j\) 求出一个有限子集 \(F_j \subseteq K_j\)，使得所有满足 \(A_j > 0\) 的 \(j \in G\) 都有 \(\sum \limits_{k \in F_j} a_{j,k} > \frac{A}{A'}A_j\)（仿佛是一只考拉告诉了我们这个不等式）。无论如何，至少是存在一个 \(A_j > 0\) 的 \(j\) 的，现在我们有 \(\sum\limits_{j \in G, k \in F_j} a_{j,k} > \sum \limits_{j \in G} \frac{A}{A'}A_j = A\)。因为 \(\{a_{j,k} \mid j \in G,k \in F_{j}\}\) 显然是 \(M = \{a_{j,k}|j \in J,k \in K_j\}\) 的有限子集，于是我们推出了矛盾，因为在假设中它是绝对收敛于 \(A\) 的。
让我们回到那只考拉告诉我们的不等式：对于 \(j \in G\)，存在 \(F_j \subseteq K_j\)，使得所有满足 \(A_j > 0\) 的 \(j \in G\) 都有 \(\sum \limits_{k \in F_j} a_{j,k} > \frac{A}{A'}A_j\)。考虑反证，如果存在 \(j \in G\) 使得 \(A_j > 0\)，且对于任意有限子集 \(F_j \subseteq K_j\)，都有 \(\sum \limits_{k \in F_j} a_{j,k} \leq \frac{A}{A'}A_j\)，因为 \(A < A'\)，于是 \(\frac{A}{A'}A_j < A_j\)，因此 \(A_j\) 不是那个最小的上界，我们产生了矛盾。
上面两段证明了 \(A\) 确实是一个上界，但是它不一定是最小的。对于任意 \(A'<A\)，我们都能够找到一个 \(M\) 的有限子集使得这个子集的和大于 \(A'\)，并且该子集可以通过选取适当的有限集合 \(G \subseteq J\) 和 \(F_j \subseteq K_j\) 产生，即，该子集形如 \(\{a_{j,k} \mid j \in G, k \subseteq F_{j}\}\)。
那么 \(\sum \limits_{j \in G} A_{j} \geq \sum \limits_{j \in G}\sum \limits_{k \in F_j} a_{j,k} = \sum \limits_{j \in G,k \in F_j} a_{j,k} > A'\)，因此对于有限子集 \(G\)，它的和大于 \(A'\)，从而 \(A'\) 不是一个上界。
利用上面的定理，我们来考虑级数
的和。因为
于是我们发现，按照不同的求和的次序会得到不同的结果，因此该级数的和一定不是绝对收敛的。
习题
1
略。
2
\(|x|\)。
3
略。
4
略。
5
第二个等号的右侧重复使用了求和下标 \(k\) 并把两个含义不同的 \(k\) 混淆。
6
\([1 \leq j \leq n](n-j+1)\)。
7
\(mx^{\overline{m-1}}\)。
8
\(\displaystyle 0(m>0),\frac{1}{|m|!} (m < 0)\)。
9
显然我们希望 \(x^{\overline{m+n}} = x^{\overline m}(x+m)^{\overline{n}}\) 对于所有整数 \(m,n\) 都成立。取 \(m = -n\)，我们有 \(1 = x^{\overline{-n}}(x-n)^{\overline{n}}\)，从而 \(x^{\overline{-n}} = \dfrac{1}{(x-n)^{\overline{n}}}\)。
10
是正确的。
11
显然。
12
分类讨论容易证明。
13
暂略。
14
15
记 \(T_n = \sum \limits_{k=1}^{n} k^3,S_n = \sum \limits_{k=1}^{n} k^2\)，首先证明 \(T_n + S_n = 2\sum \limits_{1 \leq j \leq k \leq n} jk\)：
接下来对其进行化简，上式变为
答案显而易见。\(T_n = \displaystyle \left(\frac{n(n+1)}{2}\right)^2\)。
16
化为乘积。写了个除号怎么还不认识两个分式相等了。
17
分类讨论即可。没什么用。
18
利用如下条件：对于 \(z=a+bi\)，\(a^+,a^-,b^+,b^-\leq |z|\leq a^++a^-+b^++b^-\)。
之后的部分较为显然。
19
比较显然，求和因子 \(s_n = \frac{2^{n-1}}{n!}\)，最后可以算出 \(S_n = S_0 + 3(2^n -1)\)。最后注意到 \(T_n = \frac{1}{s_na_n} S_n\)，不要漏除了 \(a_n\)，于是最后的解是 \(T_n = 3n! + \frac{n!}{2^{n-1}}\)。
20
扰动法给出 \(\sum \limits_{0 \leq k \leq n} H_k = (n+1)H_{n+1}-(n+1)\)。
21
直接扰动即可。
扰动法的本质还是，分裂 \(T_{n+1}\) 的头尾两项，从中找到关于 \(T_n\) 的表达式。
22
利用 \([1 \leq j,k \leq n] = [1 \leq j < k \leq n] + [1 \leq k < j \leq n] + [1 \leq k = j \leq n]\) 来证明。
23
注意 \(\sum \frac{1}{x+1}\delta x = H_x+C\)，是 \(\frac{1}{x+1}\) 而非 \(\frac{1}{x}\)。
两种方法都可以给出 \(H_n+H_{n+1}-1\)，或者类似的结果。
24
分部求和得到 \(1-\frac{H_{n}+1}{n+1}\)。
25
略。
26
注意到 \(\prod \limits_{1 \leq j,k \leq n} a_{j}a_k \neq \left(\prod \limits_{1 \leq j \leq n} a_j\right)\left(\prod \limits_{1 \leq k \leq n} a_k\right)\)。
意识到这点就不容易推错了，利用 \([1 \leq j \leq k \leq n]\) 的艾弗森括号变换，答案是 \(\prod \limits_{ 1\leq k \leq n} a_{k}^{n+1}\)。
27
\(\Delta(c^{\underline x}) = \frac{c^{\underline{x+2}}}{c-x}\)。
令 \(c=-2,x=x-2\) 后得到 \(\Delta(-(-2)^{\underline{x-2}}) = \frac{(-2)^{\underline x}}{x}\)，剩下的部分是简单的。
28
第三步的交换求和顺序出了问题。
在无穷和式中，我们做的一切变换都必须满足原和式绝对收敛。诚然，如果把 \(a_k = \frac{k}{k+1}-\frac{k-1}{k}\) 看成一个整体，原和式是绝对收敛的，且值为 \(1\)，但是如果把 \(a_k\) 写作两项 \(a_{k,0} = \frac{k}{k+1},a_{k,1}=- \frac{k-1}{k}\)，那么显然它不是绝对收敛的，且正负两部分都发散。这里在使用多重和式的交换求和顺序时，显然把 \(a_k\) 看作了两项，此时便不再满足原和式绝对收敛，从而我们所作的变换是没有根据的。
对于无穷和式求和的时候一定要时刻小心。