数学准备
数学归纳法
除开一般我们所说的数学归纳法，还有更为广泛应用的数学归纳法，特别的，在对于基于两个整数的命题 $ P(m,n) $ 上，或是在不可数集合的证明问题上，我们称这个原理为良值原理
良值原理
设关系 $ “\prec” $ 是集合S上的一个关系，其满足：
- 给定S中的x，y和z，如果 $ x \prec y $ 且 $ y \prec z $ ，则有 $ x \prec z $
- 给定S中的x和y，他们的关系只能在下面三选一：$ x \prec y$ ，$ x = y $ 或者 $ y \prec x $
- 如果A是S中的任何非空子集，则A中能找到一个元素x，使得对于A中所有的y，有 $ x \preceq y $
这个关系被称为良序关系
对于一般的 $ < $ 「小于关系」，在正整数范围内肯定是良序的。
数、幂和对数
和与积
我们使用和的符号 $ \sum $ 来表示和，一般的，用这样能使算式表达的更为紧凑：
$$ \sum^{n}_{j=1}a_j \qquad \text{或者} \qquad \sum^{}_{1 \leq j \leq n}a_j $$
当 $ n = 0 $ 时，上述和的值定义为0.
而我们也可以使用
$$ \sum^{}_{R(j)}a_j $$
来表示，这里j称为哑下标或下标变量
和数之积的分配律
$$ (\sum_{R(i)}a_i)(\sum_{S(j)}b_j) = \sum_{R(i)}(\sum_{S(j)}a_ib_j) $$
改变变量
$$ \sum_{R(i)}a_i = \sum_{R(j)}a_j = \sum_{R(p_{(j)})}a_{p_{(j)}} $$
交换求和的次序
$$ \sum_{R(i)}\sum_{S(j)}a_{ij} = \sum_{S(j)}\sum_{R(i)}a_{ij} $$
注意，如果S(j)与i有关，我们可以像求二元积分一样画出积分界面一样
:交换求和次序对于无穷级数并不一直成立
处理作用域
如果R(j)和S(j)是任意的关系，则有：
$$ \sum_{R(j)}a_j + \sum_{S{j}}a_j = \sum_{R(j) \cup S{j}}a_j + \sum_{R(j) \cap S{j}}a_j $$
由这些我们可以很容易证明出来几条定理：
例1.「二分法」
$$ \sum_{0 \leq j \leq n}a_j = \sum_{0 \leq j \leq n/2}a_{2j} + \sum_{0 \leq j \leq n/2}a_{2j+1} $$
例2.「三角区域求和」
$$ S = \sum_{i=0}^{n} \sum_{j=0}^{i}a_ia_j = \frac{1}{2} ((\sum_{i=0}^{n}a_i)^2 + (\sum_{i=0}^{n}{a_i}^2)) $$
例3.「几何级数的和」
$$ a + ax + \cdots + ax^n = \sum_{0 \leq j \leq n}ax^j = a(\frac{1-x^{n-1}}{1-x}) $$
例4.「算数级数的和」
$$ \sum_{0 \leq j \leq n}(a+bj) = a(n+1) + \frac{1}{2}bn(n+1) $$
括号记号和克罗内克记号 $ 「\delta」 $
括号记号:
$$ [\text{命题}] = \begin{cases} 1 & 如果命题为真\\ 0 & 如果命题为假\\ \end{cases} $$
我们对此有一些引申推导：
$$ \begin{split} \sum_{R(p(j))}a_{p(j)} &= \sum_{j}a_{p(j)}[R(p(j))] \\ &= \sum_{j}\sum_{i}a_i[R(i)][i=p(j)] \\ &= \sum_{i}a_i[R(i)]\sum_{j}[i=p(j)] \end{split} $$