跳至内容
Topos Uranos
中文 (中国)

求和、数列与归纳法

摘要

本课介绍求和记号及其性质（线性、拆分、指标平移和顺序反转），并把它应用于裂项求和以及等差数列与等比数列的求和。随后研究强归纳法和良序原理，证明归纳法蕴涵这两者，说明它们在什么意义上与归纳法等价，并用它们证明每个大于 11 的自然数都是素数的乘积。

学习目标

  1. 用求和记号书写和变换和式，运用它的线性、拆分、指标平移和顺序反转等性质。
  2. 计算裂项求和，并用它来推导而不仅仅是验证求和公式。
  3. 求等差数列或等比数列的通项与前若干项的和，并把它们应用于解题。
  4. 用强归纳法和良序原理进行证明，由归纳原理推出这两者，并说明良序原理借助哪些附加的事实可以重新得到归纳法。

求和记号

在关于皮亚诺公理的课中，出现了许多按某种规律排列的项的和，例如 1+2+⋯+n1 + 2 + \cdots + n。省略号把猜出这一规律的任务交给了读者；求和记号则把它明确写出。若 am,am+1,…,ana_m, a_{m + 1}, \ldots, a_n 是数，且 m≤nm \leq n，就写作

∑k=mnak=am+am+1+⋯+an\sum_{k=m}^{n} a_k = a_m + a_{m + 1} + \cdots + a_n

读作“aka_k 对 kk 从 mm 到 nn 求和”。字母 kk 是和的求和指标；mm 和 nn 是它的下限和上限，aka_k 是通项。这个和共有 n−m+1n - m + 1 项。指标是哑变量：和的值与用哪个字母表示它无关，所以 ∑k=1nk2\sum_{k=1}^{n} k^2 和 ∑j=1nj2\sum_{j=1}^{n} j^2 是同一个数。指标取遍自然数；而各项则可以是其他种类的数。本课中除自然数外，还出现带有负数的整数和分数，它们在下一个单元中构造：这里预先用到它们，并且只用到它们最基本的计算规则和序的规则（交换律、结合律、分配律、符号法则、减法以及除以非零数）。下面的求和性质都用这些规则证明，因此对其中任何一种数作为项都成立。

和关于自然数的运算的课中的加法、乘法和乘方一样，求和也有一个不需要省略号的递归定义：只有一项的和就是这一项，要添加一项，就把它加到前面的结果上。

∑k=mmak=am,∑k=mn+1ak=∑k=mnak+an+1\sum_{k=m}^{m} a_k = a_m, \qquad \sum_{k=m}^{n + 1} a_k = \sum_{k=m}^{n} a_k + a_{n + 1}

这个定义从 mm 开始，而递归定理按照它的叙述，是从 11 开始定义函数的。不过只需平移指标：不定义到 nn 为止的和，而定义从 qq 开始的前 ama_m 项的和。取初值 ama_m 和规则 gq(x)=x+am+qg_q(x) = x + a_{m + q}，递归定理给出唯一的函数 FF（从 N\mathbb{N} 到数），使得 F(1)=amF(1) = a_m 且 F(q+1)=F(q)+am+qF(q + 1) = F(q) + a_{m + q} 对每个自然数 qq 成立。于是对 n≥mn \geq m，把到 nn 为止的和定义为 FF 在它的项数 n−m+1n - m + 1 处的值，这个项数是自然数，因为 m<n+1m < n + 1：

∑k=mnak=F(n−m+1)\sum_{k=m}^{n} a_k = F(n - m + 1)

取 n=mn = m 得到 F(1)=amF(1) = a_m；取 q=n−m+1q = n - m + 1，由于 m+q=n+1m + q = n + 1，等式 F(q+1)=F(q)+am+qF(q + 1) = F(q) + a_{m + q} 恰好就是定义的第二条规则。由此，从 mm 开始的递归定义对每个 n≥mn \geq m 确定唯一的和，并且当 m=1m = 1 时，它与递归定理直接给出的和一致，因为这时 F(n)=∑k=1nakF(n) = \sum_{k=1}^{n} a_k。

用这种记号，在关于皮亚诺公理的课中用归纳法证明的公式，即前 nn 个自然数之和的公式，写作：

∑k=1nk=n(n+1)2\sum_{k=1}^{n} k = \frac{n(n + 1)}{2}

平方和 ∑k=1nk2\sum_{k=1}^{n} k^2 是下一步，而本课不会只限于验证它：关于裂项求和的那一节将在事先不知道它的情况下把它推导出来。

对和的上限所作的归纳从下限 mm 开始，而下限未必是 11。然而皮亚诺公理中的归纳原理从 11 开始；要从别的自然数开始，需要下面的引理。

引理从任意自然数开始的归纳法

设 n0n_0 是一个自然数。若某性质对 n0n_0 成立，并且在承认它对任意自然数 k≥n0k \geq n_0 成立之后，它对 k+1k + 1 也成立，则该性质对所有自然数 n≥n0n \geq n_0 成立。思路是从 n0n_0 起给自然数重新编号，以回到通常的归纳原理。要用到关于自然数运算的课中的引理，即每个不等于 11 的自然数都是某个数的后继，以及加法的单调性。图中 n0=4n_0 = 4，p=3p = 3：从 n0n_0 起，每个自然数下方标出它的新编号 qq。

证明

  1. n0=p+1,Q(q)↔P(p+q)n_0 = p + 1, \quad Q(q) \leftrightarrow P(p + q)

    若 n0=1n_0 = 1，这就是归纳原理。否则，n0=p+1n_0 = p + 1 对某个自然数 pp 成立，我们考虑性质 QQ，它断言 PP 对 p+qp + q 成立。

  2. Q(1)↔P(p+1)↔P(n0)Q(1) \leftrightarrow P(\resaltar{p + 1}) \leftrightarrow P(\resaltar{n_0})

    性质 QQ 对 11 成立，因为 Q(1)Q(1) 就是 P(n0)P(n_0)。

  3. P(p+q)→P((p+q)+1)=P(p+(q+1))P(p + q) \rightarrow P(\resaltar{(p + q) + 1}) = P(\resaltar{p + (q + 1)})

    若 Q(q)Q(q) 成立，由于 1≤q1 \leq q，由加法的单调性得 p+q≥p+1=n0p + q \geq p + 1 = n_0，于是所给的一步可应用于 k=p+qk = p + q：Q(q+1)Q(q + 1) 成立。

  4. n≥n0→(∃q∈N)(n=p+q)n \geq n_0 \rightarrow (\exists q \in \mathbb{N})(n = p + q)

    由归纳原理，Q(q)Q(q) 对每个 qq 成立。每个 n≥n0n \geq n_0 都具有 p+qp + q 的形式：若 n=n0n = n_0，则取 q=1q = 1；若 n=n0+ln = n_0 + l，则取 q=1+lq = 1 + l。

求和的性质

由递归定义，对上限作归纳，可以推出下列性质，它们对任意的项 aka_k 和 bkb_k 以及任意的数 cc 都成立：

  1. 线性：∑k=mn(ak+bk)=∑k=mnak+∑k=mnbk\sum_{k=m}^{n} (a_k + b_k) = \sum_{k=m}^{n} a_k + \sum_{k=m}^{n} b_k 且 ∑k=mnc ak=c∑k=mnak\sum_{k=m}^{n} c\,a_k = c \sum_{k=m}^{n} a_k。特别地，把一个常数加 nn 次就是把它乘以 nn：∑k=1nc=nc\sum_{k=1}^{n} c = nc。
  2. 拆分：若 m≤p<nm \leq p < n，则 ∑k=mnak=∑k=mpak+∑k=p+1nak\sum_{k=m}^{n} a_k = \sum_{k=m}^{p} a_k + \sum_{k=p+1}^{n} a_k。
  3. 指标平移：对每个自然数 pp，∑k=mnak=∑j=m+pn+paj−p\sum_{k=m}^{n} a_k = \sum_{j=m+p}^{n+p} a_{j - p}。
  4. 顺序反转：∑k=1nak=∑j=1nan+1−j\sum_{k=1}^{n} a_k = \sum_{j=1}^{n} a_{n + 1 - j}。
定理求和的性质

对任意的项 aka_k 和 bkb_k 以及任意的数 cc，求和是线性的，可以拆分为两个相接的和，并且允许指标平移和顺序反转，具体如上面的列表所示。每条性质都对上限作归纳来证明，借助前面的引理，这一归纳从下限开始。只用到递归定义以及加法和乘法的性质；顺序反转还要用到拆分和平移。

证明

  1. ∑k=mn+1(ak+bk)=∑k=mnak+∑k=mnbk+(an+1+bn+1)=∑k=mn+1ak+∑k=mn+1bk\sum_{k=m}^{n + 1} (a_k + b_k) = \resaltar{\sum_{k=m}^{n} a_k + \sum_{k=m}^{n} b_k} + (a_{n + 1} + b_{n + 1}) = \sum_{k=m}^{n + 1} a_k + \sum_{k=m}^{n + 1} b_k

    线性。当 n=mn = m 时，两边都等于 am+bma_m + b_m。若它对 nn 成立，则应用递归定义、归纳假设以及加法的结合律和交换律。同样地，借助分配律可证 ∑k=mnc ak=c∑k=mnak\sum_{k=m}^{n} c\,a_k = c \sum_{k=m}^{n} a_k，以及 ∑k=1nc=nc\sum_{k=1}^{n} c = nc，因为 nc+c=(n+1)cnc + c = (n + 1)c。

  2. ∑k=mp+1ak=∑k=mpak+ap+1=∑k=mpak+∑k=p+1p+1ak\sum_{k=m}^{p + 1} a_k = \sum_{k=m}^{p} a_k + \resaltar{a_{p + 1}} = \sum_{k=m}^{p} a_k + \resaltar{\sum_{k=p+1}^{p + 1} a_k}

    拆分，固定 pp，对 nn 从 p+1p + 1 开始作归纳。当 n=p+1n = p + 1 时，这就是递归定义，因为只有一项的和就是这一项。

  3. ∑k=mn+1ak=∑k=mpak+∑k=p+1nak+an+1=∑k=mpak+∑k=p+1n+1ak\sum_{k=m}^{n + 1} a_k = \resaltar{\sum_{k=m}^{p} a_k + \sum_{k=p+1}^{n} a_k} + a_{n + 1} = \dato{d}{\sum_{k=m}^{p} a_k + \sum_{k=p+1}^{n + 1} a_k}

    若拆分对 nn 成立，就在两边加上项 an+1a_{n + 1}，并对每个和应用递归定义。

  4. ∑j=m+pn+1+paj−p=∑j=m+pn+paj−p+an+1=∑k=mnak+an+1=∑k=mn+1ak\sum_{j=m+p}^{n+1+p} a_{j - p} = \resaltar{\sum_{j=m+p}^{n+p} a_{j - p}} + a_{n + 1} = \resaltar{\sum_{k=m}^{n} a_k} + a_{n + 1} = \dato{s}{\sum_{k=m}^{n + 1} a_k}

    平移。当 n=mn = m 时，两边都等于 ama_m。若它对 nn 成立，由于上限 (n+p)+1(n + p) + 1 就是 (n+1)+p(n + 1) + p，应用递归定义和归纳假设。

  5. ∑j=1n+1an+2−j=an+1+∑j=2n+1an+2−j=an+1+∑i=1nan+1−i\sum_{j=1}^{n + 1} a_{n + 2 - j} = a_{n + 1} + \resaltar{\sum_{j=2}^{n + 1} a_{n + 2 - j}} = a_{n + 1} + \resaltar{\sum_{i=1}^{n} a_{n + 1 - i}}

    顺序反转，对 nn 作归纳。当 n=1n = 1 时，两边都等于 a1a_1。若它对 nn 成立，就用拆分把反序和（共 n+1n + 1 项）的第一项分出来，并把指标平移一位，取 j=i+1j = i + 1。

  6. an+1+∑i=1nan+1−i=an+1+∑k=1nak=∑k=1n+1aka_{n + 1} + \resaltar{\sum_{i=1}^{n} a_{n + 1 - i}} = a_{n + 1} + \resaltar{\sum_{k=1}^{n} a_k} = \sum_{k=1}^{n + 1} a_k

    由归纳假设，最后那个和等于 ∑k=1nak\sum_{k=1}^{n} a_k；由交换律和递归定义，得到 n+1n + 1 时的顺序反转。

线性使我们能把复杂的和化为已知的和。后两条性质是变量替换：平移令 k=j−pk = j - p，以另一种编号取遍同样的项；顺序反转令 k=n+1−jk = n + 1 - j，从最后一项到第一项取遍它们。然而，求和对乘积的表现并不一样：乘积之和不是和之积。只需一个两项的例子，取 ak=bk=ka_k = b_k = k：

∑k=12k⋅k=1+4=5≠9=(1+2)(1+2)\sum_{k=1}^{2} k \cdot k = 1 + 4 = 5 \neq 9 = (1 + 2)(1 + 2)
命题前若干个奇数之和

证明前 nn 个奇数之和是 n2n^2。线性把这个和化为两个已知的和，无需新的归纳。

证明

  1. 1+3+5+⋯+(2n−1)=∑k=1n(2k−1)1 + 3 + 5 + \cdots + (2n - 1) = \dato{s}{\sum_{k=1}^{n} (2k - 1)}

    位于第 kk 位的奇数是 2k−12k - 1：第一个是 11，第二个是 33，第 nn 位的是 2n−12n - 1。所求的和写作如下。

  2. ∑k=1n(2k−1)=2∑k=1nk−∑k=1n1\sum_{k=1}^{n} \resaltar{(2k - 1)} = \resaltar{2 \sum_{k=1}^{n} k - \sum_{k=1}^{n} 1}

    由线性，这个和分成两个：各个 kk 之和的两倍，减去 nn 个一之和。

  3. 2∑k=1nk−∑k=1n1=n(n+1)−n2 \resaltar{\sum_{k=1}^{n} k} - \resaltar{\sum_{k=1}^{n} 1} = \resaltar{n(n + 1)} - \resaltar{n}

    第一个和是前 nn 个自然数之和 n(n+1)2\frac{n(n + 1)}{2}，因子 22 约去了它的分母；第二个和是 nn 个数 11 相加。

  4. n(n+1)−n=n2+n−n=n2\resaltar{n(n + 1)} - n = \resaltar{n^2 + n} - n = n^2

    展开乘积；项 nn 与 −n-n 相互抵消。

  5. k2−(k−1)2=2k−1k^2 - (k - 1)^2 = 2k - 1

    图说明了其中的道理：每个奇数都是两个相邻平方数之差，即把边长为 k−1k - 1 的正方形变成边长为 kk 的正方形的那块曲尺形。