Chapter 2 笔记
因为 \(\sum\) 实在是太多了所以咱的 \(\sum\) 都是用绑的 <Leader>+su 快捷键写的（
为了方便之后查阅，会一定程度的标注对应英文名词，按照章节分类。
随意记录的东西，估计不是那么规范，主要还是自用。
2.1 记号 Notationψ(｀∇´)ψ
具体数学里喜欢用 \(k\) 来当第一个使用的枚举变量，因为 \(i\) 被用来代表虚数单位。
感觉上来说确实蛮有道理，用 \(k\) 似乎也比较好看，之后的笔记也就参照这个标准来用 \(k\) 当作 index 了。
一般的和式有确定界限，类似 \(\sum\limits_{k = l}^{r} a_{k}\) 的形式。
也可以写作 \(\sum\limits_{\text{Cond}(k)}^{} a_{k}\) 表示对于所有满足 \(\text{Cond}(k)\) 条件的 \(a_{k}\) 求和。
当然你甚至可以用 Iverson Bracket 乘上你的被加数(summand)：\(\sum\limits_{}^{} a_{k}[\text{Cond}(k)]\)。
Iverson 括号大概是说，对于命题 \(P\)：
具体数学中似乎为了定义的严谨性，求和一般是从 \(0\) 开始的，这似乎要到之后才能解释。
那么也就等到之后再来详细叙述吧。
不过 Iverson Bracket 也可以很好的帮助处理 \(a_{0}\) 项，具体方式是，对于没有定义的条件，我们让 Iverson Bracket 返回 \(0\)，这样就可以规避掉不少问题了！甚至还能够简化式子。
比如你需要表示 \(\le N\) 的素数的倒数之和：
\(\sum\limits_{p}^{}[p\text{ is a prime}][p \le N] / p\)
因为我们处理的时候通常按顺序处理连乘的每一项，\(0\) 在第一个括号就寄了，准确一点说这应该是约定俗成的。
于是我们可以直接返回 \(0\)，跳过这个项(term)的后半部分。
2.2 和式和递归式 Sums and Recurrencesψ(｀∇´)ψ
因为我没看 Chapter 1，所以 skip 掉了。
2.3 和式的处理 Manipulation of Sumsψ(｀∇´)ψ
对于和式，我们有三条简单且重要的运算律：
- 分配律(distributive law)： \(\sum\limits_{k \in S}^{}ca_{k} = c\sum\limits_{k \in S}^{}a_{k}\)。
- 结合律(associative law)：\(\sum\limits_{k \in S}^{}a_{k} + \sum\limits_{k \in S}^{}b_{k} = \sum\limits_{k \in S}^{}a_{k} + b_{k}\)。
- 交换律(commutative law)：\(\sum\limits_{k \in S}^{}a_{k} = \sum\limits_{p(k) \in S}^{}a_{p(k)}\)。
第一条的作用大约就是把常数项移除某一个 \(\sum\)。
第二条的作用则是合并两个界限相同的 \(\sum\)。
第三条看着有点怪，似乎和我们平常说的交换律不太一样。
但是实际上没有本质区别（只不过这种描述更形式化，利于思考），我们可以把 \(k\) 替换成一个基于 \(S\) 生成的映射 \(p(k)\)，且所有 \(p(k)\) 也如同所有 \(k\) 一样构成了集合 \(S\) 的一个排列(permutation)；
这点非常重要，类似于一一映射，如果不满足这个条件，等式是无法成立的。
众所周知的求等差级数(arithmetic progression)的，据信是高斯小时候提出来的公式，实际上可以用这个做解释。
我们考虑做一下变量代换，运用交换律，令 \(p(k) = n - k\)（这实际上就是倒过来求和）：
我们希望得到的公式是不包含我们所枚举的 \(k\) 的。
注意到 \(\sum\limits_{k = 0}^{n}(a + bk)\) 中有 \(+bk\)，等号右边有 \(-bk\)，尝试加起来：
这就是“首项加末项乘项数除以2”的形式，当然扩展也很容易，在此略去不提。
这样的操作看起来不是那么的自然，但是仔细思考，关键的一步就在于消去变量 \(k\)，而和式的基本运算律已经告诉了我们可以将此处的 \(k\) 替换为 \(n - k\)，这就有了将它消去的基础。
当然，就算带上系数，这种方法仍然是适用的，毕竟只需要更改 \(Sum\) 前的系数就行了（这和后面的扰动法有点类似）。
有些时候交换律也可以用于放松排列的限制。
比如我们对于所有偶数项求和，可能会写成：\(\sum\limits_{\substack{k \in S \\ k\text{ even}}}^{}a_{k}\)。
感觉 \(k \text{ even}\) 放在这里很烦，我们希望的是每一个 \(\sum\limits_{}^{}\) 都只有一个限制条件。
当然，可以用 Iverson Bracket 放到后面，不过那样其实还是不太优雅。
我们可以建立映射 \(p(k) = 2k\)，枚举 \(p(k)\)：\(\sum\limits_{\substack{2k \in S \\ 2k \text{ even}}}^{}a_{2k}\)，因为 \(2k\) 不管 \(k\) 怎么取都是一个偶数（这意味着我们只需要满足 \(2k \in S\) 的条件），所以我们可以写成 \(\sum\limits_{2k \in K}^{}a_{2k}\)。
有一个很显然的式子，假设 \(S,S^\prime\) 是两个整数集。
那么 \(\sum\limits_{k \in S}^{}a_{k} + \sum\limits_{k \in S^\prime}^{}a_{k} = \sum\limits_{k \in S \cap S^\prime}^{}a_{k} + \sum\limits_{k \in S\cup S^\prime}^{}a_{k}\)。
感觉没啥好说的。
扰动法，高中数学教数列的时候也会提到这种方法，只不过被广泛的称作另一个名字——“错位相减法”。
主要用于求解一些和式的封闭形式。
具体来说，对于一个和式 \(S_{n} = \sum\limits_{k = 0}^{n} a_{k}\)，我们将它写成两种不同的形式（一般是分别将首项和末项分离开来），然后尝试化简出封闭形式。
形象一点的话就长这样：
之后要做的事情大约就是，尝试把右边的 \(\sum\limits_{}^{}\) 写成与 \(S_{n}\) 相关的形式，把 \(a_{0}, a_{n + 1}\) 单独放在一边。
最经典的例子就是等差数列求和，或者说，求几何级数(geometric progression)的和。
即 \(S_{n} = \sum\limits_{k = 0}^{n}a_{0}q^{k}\)。
可以照猫画虎写出：
只需要把 \(1 - q\) 除到右边，我们就能得到 \(S_{n}\) 的封闭形式 \(S_{n} = \dfrac{a_{0} - a_{0}q^{n + 1}}{1 - q}\)，当然，\(x \neq 1\)。
还能再给力点吗？比如 \(a_{k} = kx^k\) 的 \(S_{n}\)，其中 \(x\) 为常数。
其中 \(G_{n}\) 是几何级数 \(\sum\limits_{k = 0}^{n}x_{k}\) 的和。
于是我们很容易写出 \(S_{n} = \dfrac{\dfrac{1 - x^{n + 1}}{1 - x} - (n + 1)x^{n + 1} }{1-x} = \dfrac{x - (n + 1)x^{n + 1} + nx^{n + 2}}{(1 - x)^2}\)，不要忘记 \(x \neq 1\)。
当然，后者还有另一种推导方式，注意到 \(kx^{k}\) 一股子求完导之后的味道：
于是我们对 \(G_{n} \Rightarrow \sum\limits_{k = 0}^{n}x^{k} = \dfrac{1 - x^{n + 1}}{1 - x}\) 两边求导：
\(\sum\limits_{k = 0}^{n}kx^{k - 1} = \dfrac{(1 - x)(-(n + 1)x^{n}) + 1 - x^{n + 1}}{(1 - x)^2}\)，展开后似乎就是我们想要的式子。