下载掌阅APP，畅读海量书库
立即打开
前 n 项2的幂的和是多少？
像以往一样，解决问题的第一步是确信你理解了问题的含义。什么是2的幂？形如2 3 （就是8），是2的指数为某个整数的结果。好了，那么 n 是什么？不用说， n 是任意的使问题有意义的东西。问题是要把某些对象加起来， n 是加在一起的对象的数量。所以 n 必须是一个表示全部量的变量，例如10。最后，我们需要确定前 n 项2的幂是哪些。第一项2的幂是2 0 ，还是2 1 ，或者其他什么？在计算机科学中，我们通常从0开始计数。
知道了 n 的值，我们就可以计算出答案。例如，在 n =10的情况下，问题是要求出下式的值：
2 0 +2 1 +2 2 +2 3 +2 4 +2 5 +2 6 +2 7 +2 8 +2 9
=1+2+4+8+16+32+64+128+256+512
答案是1023。
我们并不只是要对 n =10的情况求和。问题是以变量 n 陈述的，所以我们希望答案的形式与该变量相关。换句话说，我们的答案应该是泛化的公式，对于任意 n 都适用。特别地，适用于下式：
2 0 +2 1 +2 2 +…+2 n -1
求和的每个元素都称为 项 （term），因此在上式中，2 0 ,2 1 ,…,2 n -1 都是项。注意：最后一项是2 n -1 ，而不是2 n 。我们是从0开始计数的，因此前 n 项2的幂是指2的0,1,2,…, n -1次幂， n 项中的最后一项是2 n -1 。
三个点…称为 省略号 （ellipsis）。省略号给出了一种模式，表示对读者是显而易见的。但是“显而易见”是心理感受，读者未必会与作者有同样的感受。如果我们只有如下公式：
省略的项显而易见吗？又省略了多少项呢？“显而易见”不是事实。我们在之前确定了要讨论对2的幂求和，如果只给你带省略号的式（3-1），那么对缺失项的推断就不止一种结果。可以有这样的推断：第二项比第一项大1，第三项比第二项大2，以此类推。在这种情况下，第四项应该比第三项大3，即7。那么结果可以是
而不是
1+2+4+8+16+32+…+512
需要弄清楚512是否真的是式（3-2）中的序列中的最后一个数（见习题3.10）。
避免上述情况中模糊含义的解决方法就是找到典型项的表达式，并且使用求和表示法来表示要相加的是哪些项。典型的2的幂看起来形如2 i ——我们需要一个不同于 n 的变量名作为指数，因为 n 已经被用来表示相加的项数。则上式中的前 n 项和可以无歧义地表示为
“∑”是大写希腊字母sigma，表示求和。
与省略号表示法不同，求和表示法没有留下任何其他想象的空间。即使在 n =1或 n =0的情况下，它也是有意义的。当 n =1时，式（3-3）变为
即对第一项求和。当 n =0时，求和的上限小于下限，此时式（3-3）变成对第0项求和，按照约定结果为0：
再举一个例子，前 n 个奇数的和如何表示？奇数表示为2 i +1，第一个奇数是1，即当 i =0时2 i +1的值。所以前 n 个奇数的和可以记为 [1]
现在回到本章开始的问题。我们能找到一个与式3-3等价的简单公式（不带省略号与求和符号）吗？
面对这样的问题（当你确定理解了问题之后），首先要做的是尝试几个例子，这有助于清楚你的理解为什么正确。在证明定理2.4时，使用了同样的策略。先代入 n =1，2，3，得到
1、3、7分别比2、4、8小1，它们的后继数都是2的幂。在构造假设之前，最好再试一次：
15比16小1，是下一项2的幂。至此我们还没有做什么证明，但是这种模式似乎太有规律而不像是巧合。我们来推测一下：
我们的推测对吗？右侧或许是2 n -1 -1，也或许是2 n +1 -1呢？再代入 n =4来确认。在 n =4的情况下，式（3-6）的左端与式（3-5）相同，即为15，而式（3-6）的右端为2 4 -1=15。所以，看起来式（3-6）是一个正确的推测。即使在 n =0的情况下，它也是可行的：
左端 i 的结尾值小于 i 的开始值，是一个零项求和，即0。
这些还不足以成为一个证明。还需要进一步观察从式（3-4）到式（3-5）是怎样 过渡 的。也就是说，如果2 3 加到2 3 -1上，则右端是2 3 +2 3 -1=2·2 3 -1=2 4 -1。
一般来说“2的幂再加上其自身会得到其后继2的幂”是成立的。所以假设我们已知式（3-6）对于一个给定的 n 是成立的。在归纳法中，这个假设被称为 归纳假设 （induction hypothesis）。归纳法的关键步骤 ——归纳步骤 （induction step）是证明如果 归纳假设 是真的，那么下一个值（用 n +1替换了 n ）也是真的。下面是归纳步骤：
这正是用 n +1替换 n 后，式（3-6）的结果。
这是 数学归纳法证明 （proof by mathematical induction）的一个经典示例。术语“归纳”的含义是指命题关于某一个值（例如 n ）为真，蕴含着该命题对 n +1也为真，从而有命题对于任意值都为真，那么对于任意更大的值，也为真。与此相类似，如果我们有了一个万无一失的方法可以从梯子的一级台阶登上更高一级台阶，那么我们就能够到达第一级台阶之上的任何一级台阶（见图3.1）。
这里给出数学归纳法证明的一般形式（见图3.2）。
图3.1 用阶梯比喻数学归纳法。如果你能（归纳基础）登上梯子的最底部台阶，并且根据假设（归纳假设）你已经到达了任意的某个台阶，那么你能够（归纳步骤）登上下一个台阶。因此（结论）你可以到达任意一级台阶
图3.2 数学归纳法原理。首先证明归纳基础 P （ n 0 ）（浅灰色），然后证明如果 P （ n ）为真（灰色最后的值），那么 P （ n +1）也必为真（黑色的值）
下面证明谓词 P （ n ）对于大于或等于某个特定数 n 0 的任意数 n 都成立：
归纳基础 。证明 P （ n 0 ）成立。
归纳假设 。设任意 n 是大于或等于 n 0 的某个数，假设 P （ n ）成立。
归纳步骤 。假设 归纳假设 为真，证明 P （ n +1）成立。
应用上述模式证明式3-6的推测，隐去所有我们为找到通用谓词而分析的特殊情况和猜想。
例3.8 对于任意的 n ≥0，
解 ：按照归纳模式，谓词 P （ n ）为
并且 n 0 =0。
归纳基础 。 P （0）表示命题
成立，因为方程的左右两端都等于0（参见式3-7）。
归纳假设 。假设 P （ n ）成立，即
对于任意选定的 n 值（ n ≥0）成立。
归纳步骤 。我们需要证明 P （ n +1）成立，即
分离出最后一项为相加项，式（3-9）的左侧为
其中项正好是 归纳假设 P （ n ），等于2 n -1。因此，要完成式（3-9）的证明，我们只需要再证明
因为2 n +2 n =2 n +1 ，所以上式成立。■
数学归纳法是强有力的证明技术且应用广泛，如下例所示。
例3.10 对于任意n ≥0， 有
解 ：设谓词 P （ n ）为
归纳基础
。令
n
0
=0，等式左端的和是空项，其值为0；右端表达式是
，值也为0。即
P
（0）成立。
归纳假设 。假设 P （ n ）为
对于任意选定的 n 值（ n ≥0）成立。
归纳步骤 。我们需要证明 P （ n +1）成立，即
再次将左端的最后一项分离为相加项，可以应用 归纳假设 如下：
有时，一个规范的证明不足以表达直觉的感受，因为我们不清楚做符号变换的原因。给出一个具体的解释或许会更令人满意。对于式（3-12）（以及许多其他求和问题）的几何解释是一个由黑灰色块覆盖的网格。
图3.3 有多少黑块？我们有两种计算方式：对数字1,…, n 求和或计算网格面积的一半。因此这两个值必然相等
图3.3就是当
n
=5时，式（3-12）的几何表示。第一行有
n
个黑块，下一行有
n
-1个黑块，…，最后一行有1个黑块。因此，黑块的数量为
。我们用另一种方法来计算它的值。网格的长为
n
+1，高为
n
，其中一半是黑块（比较黑灰两色的形状，可以发现旋转一下完全相同），所以黑块的数量是矩形面积的一半，即
。
对于
归纳步骤
，我们也可以给出相应的几何解释。
归纳假设
是
。在归纳步骤中，我们增加了
n
+1个方块，最后的总和是
。图3.4展示了一个（
n
+1）×（
n
+2）的网格，左上半部分为黑色和浅灰色，右下半部分为灰色。图3.4中的黑色部分与图3.3中的黑色部分完全匹配，黑色部分与增加的对角线上
n
+1个浅灰块一起覆盖了新的（
n
+1）×（
n
+2）网格的一半。
图3.4 从覆盖一半的长为 n +1、宽为 n 的网格开始，增加 n +1个浅灰色块，从而达到覆盖长为 n +2、宽为 n +1新网格的一半区域
有时我们想表示一个序列值的乘积，而不是求和。乘积的表示法是用大写希腊字母pi，即∏，它的作用类似于求和∑。例如，例1.6中的公式可以记为
如同求和中的元素被称作项一样，乘积中相乘的元素被称为
因子
（factor）。上面乘积中的因子有
，…，
。
尝试一下有关乘积命题的归纳模式。
例3.13 对于任意 n ≥1，有
举例来说，在 n =3的情况下，式（3-14）变换为
再变换一下形式更易于理解：
每个分数的分子与下一个分数的分母相等，所以除了最后一个分子，其他分子都被约掉了。应用归纳法可以证明这个论点。
解 ：设谓词 P （ n ）表示为
归纳基础 。 n 0 =1，式（3-15）为
成立，因为两边都等于2。
归纳假设 。假设对于某个 n ≥1， P （ n ）成立，即
归纳步骤 。进一步计算 P （ n +1），式（3-15）的左端变为
所证为真。■
若约定零个因子的乘积为1，那么等式（3-14）在 n =0的情况下，也是有意义的，即
为什么这样的约定是有意义的呢？在零项求和时我们有类似的约定，即它的和为0。凭直觉可知，如果在一些项求和的基础上再加上零项，那么就等于加上了0。类似地，如果在一些因子乘积的基础上再乘以零个因子，那么等同于乘以1。
归纳法也可用于证明数字之外的事物。在计算机科学中，我们经常会遇到由0和1构成的序列，称0和1为两个
位
（bit）
，若干位的序列是一个
二进制字符串
（binarystring），也称为
位串
（bitstring或bitofstring）。例如，10001001是一个
长度
（length）为8的字符串。一个位串的
补
（complement）是将1和0互换的结果。例如，10001001的补是01110110。两个位串的
串联
（concatenation）是指将一个位串接到另一个位串上，例如，10001001和111的串联是10001001111。两个位串串联的长度是它们的长度之和，即8+3=11。
存在一个有趣的位串序列被称作Thue
序列
（Thuesequence
），定义如下：
T 0 =0，对于任意的 n ≥0，
T n +1 = T n 与 T n 补的串联
这是一个 归纳定义 （inductive definition）[也称为 递归定义 （recursive definition）]的示例。 T 0 定义为 基础实例 （base case），而用 T n 来定义的 T n +1 是 构造实例 （constructor case）。我们来看看Thue序列前几个字符串的定义。
0 . T 0 =0，这是基础实例。
1 . T 1 是将 T 0 （即0）与 T 0 的补（即1）串联，所以 T 1 =01。
2 . T 2 是将 T 1 （即01）与 T 1 的补（即10）串联，所以 T 2 =0110。
3 . T 3 是将 T 2 （即0110）与 T 2 的补（即1001）串联，所以 T 3 =01101001。
4 . T 4 是将 T 3 （即01101001）与 T 3 的补（即10010110）串联，所以 T 4 =0110100110010110。
对于任意的 n ≥0， T n 是 T n +1 的前半部分，因此我们可以定义一个无穷位串 t 0 t 1 t 2 …，其中 t i 是 T n 的第 i 位，且所有的 n 都足够大，使得 T n 至少有 i 位。例如，当 i =4时， T 0 、 T 1 和 T 2 的长度少于5位。但是对于所有的 n ≥3都有 T n 的长度至少为5，并且它们具有相同的第5位，即 t 4 都是1。
Thue序列具有某些非常有趣的性质。它看上去像是重复的，但并不重复；它看上去像是随机的，但并不是随机的。我们用数学归纳法来证明几个简单的性质。
Thue序列的前几个字符串：
T 0 =0
T 1 =01
T 2 =0110
T 3 =01101001
T 4 =0110100110010110
例3.16 对于任意的 n ≥0， T n 的长度是2 n 。
解 ：我们应用归纳法来证明这一点。
归纳基础 。 n 0 =0， T n 0 = T 0 =0，其长度为1=2 0 =2 n 0 。
归纳假设 。假设 T n 的长度是2 n 。
归纳步骤 。 T n +1 是由 T n 与其补串联而成，而这两个字符串的长度都是2 n ，所以 T n +1 的长度是2 n +2 n =2 n +1 。■
例3.17 对于任意的 n ≥1， T n 以 01开头，如果 n 是奇数，则以01结尾；如果 n 为偶数，则以10结尾。
解 ： T 1 =01，所以对于每个 n ≥1，都有 T n 的前两位是01。下面应用归纳法证明怎样得到 T n 的结尾。
归纳基础 。 n 0 =1。1是奇数，并且有 T n 0 = T 1 =01，即以01结尾。
归纳假设 。对于某个 n ≥1，假设当 n 为奇数时， T n 以01结尾；当 n 为偶数时，则以10结尾。
归纳步骤 。 T n +1 是以 T n 最后两位的补结束，如果 n 为奇数，则 n +1为偶数；如果 n 是偶数，则 n +1为奇数。因此，如果 n +1是奇数，则 T n +1 以01结尾；如果 n +1为偶数，则 T n +1 以10结尾。■
例3.18 对于任意的n≥0， T n 中连续的 0 或连续的 1 永远不会多于两个 。
解 ： T 0 只有一位，所以命题对于 T 0 是成立的。我们从 n 0 =1开始使用归纳法。
归纳基础 。 n 0 =1。那么 T n 0 = T 1 =01，由于没有连续的相同位，因此肯定没有连续的相同位超过两个。
归纳假设 。对于某个 n ≥1，假设 T n 中不存在超过两个连续的相同位。
归纳步骤 。 T n +1 的前半部分来自 T n ，后半部分来自 T n 的补。根据 归纳假设 ，两者中都没有000或111。因此，如果其中之一的任何情况发生，必然出现在连接处，即一个位串包含两位，另一个位串包含一位。而根据例3.17可知，在连接处的四位只能是0110或1010，这两种情况都不包含连续三个相同位（见图3.5）。■
图3.5 由 T 1 与 T 1 的补构造 T 2 ，由 T 2 与 T 2 的补构造 T 3 ，再由 T 3 与 T 3 的补构造 T 4 。灰色位是黑色位的补。如果黑色位和灰色位都不包含000或111的位串，那么这种位串就是由连接而产生的，一定在连接处的四位窗口中。而这四位总是0110或1010
我们将在习题3.11和习题11.11中再讨论Thue序列的其他性质。
我们可以用数学归纳法来证明鸽笼原理（第1章）。这需要变通一下，因为鸽笼原理中没有提到可以进行归纳的特定数字 n ，通常，我们称之为 归纳变量 （induction variable），在前面的归纳示例中用 n 来表示。
例3.19 如果有 f ： X → Y 并且| X |>| Y |，那么存在元素 x 1 ， x 2 ∈ X ，使得 x 1 ≠ x 2 且 f ( x 1 )= f ( x 2 )。
解 ：为了能够用归纳法证明，我们必须要确定归纳变量。这里有两种比较明显的可能：集合 X 的大小和集合 Y 的大小。两者都可以用，但证明会有所不同。让我们对| X |进行归纳，并重申：对于任意的 n ≥2， P （ n ）都为真，其中 P （ n ）表示
对于任意有穷集 | X | 和 | Y |， 其中 | X |＞ Y ， 并且 X = n ， 如果有 f ： X → Y ， 则存在不同的元素 x 1 ， x 2 ∈ X ， 使得 f （ x 1 ）= f （ x 2 ）。
习题3.2使用了 Y 的大小（而不是 X 的大小）作为归纳变量。
归纳基础 。 n 0 =2。如果| X |＞| Y |且 X =2，并且存在一个从 X 到 Y 的函数 f ，那么 Y 必须等于1。首先， Y 必须包含至少一个元素，因为对于每个 x ∈ X ，有 f （ x ）∈ Y ；其次， Y 不能包含多于1个元素，原因是| Y |＜| X |。从而， X 的两个元素必须都映射到 Y 的唯一元素，得证。
归纳假设 。假设对于任意的某个 n ≥2， X 和 Y 为任意有穷集，使得| X |>| Y |和| X |= n ，如果有 f : X → Y ，则存在不同的元素 x 1 , x 2 ∈ X ，使得 f ( x 1 )= f ( x 2 )。
归纳步骤 。我们要证明的是：如果| X |>| Y |和| X |= n +1，并且 f : X → Y ，则存在不同的元素 x 1 , x 2 ∈ X ，使得 f ( x 1 )= f ( x 2 )。
任选元素 x ∈ X ，有两种可能（接下来是情况分析）。要么存在另一个元素 x ′∈ X ，使得 x ′≠ x ，但是 f （ x ′）= f （ x ）；要么不存在这样的 x ′。第一种情况见图3.6， 归纳步骤 成立，我们找到了 X 的两个不同元素都映射到 Y 的同一元素。在第二种情况中， x 是集合 X 中 f 的值为 f （ x ）的唯一一个元素（见图3.7）。设 X ′是从 X 中去除 x 后得到的集合， Y ′是从 Y 中去除 f （ x ）后得到的集合。现在有| X′ |= n 且| Y′ |= Y -1＜ n ，应用 归纳假设 。 f ′： X ′→ Y ′是一个从大小为 n 的集合到更小集合上的函数，对于 X ′中的元素， f ′与 f 的函数值相同。由 归纳假设 可得存在不同的元素 x 1 ， x 2 ∈ X ，使得 f ′（ x 1 ）= f ′（ x 2 ）∈ Y ′。那么 x 1 和 x 2 也是 X 的不同成员，且具有相同的 f 值。■
图3.6 归纳法证明鸽笼原理。情况1: x 与 x ′是 X 中的不同元素， f 将它们都映射为 f ( x )
图3.7 归纳法证明鸽笼原理。情况2: x 是 X 中唯一一个将其映射为 f （ x ）的元素。然后从 X 中移除 x ，从 Y 中移除 f （ x ），再对函数 f ′: X ′→ Y ′应用 归纳假设 ，此时| X ′|=| X |-1
• 求和表示法用于表达一系列项的和。例如，表达式
表示对项2
i
求和，其中
i
值的范围从0到
n
-1。
• 约定零项之和为0。
• 归纳法 由三部分组成：
归纳基础 。证明谓词对特定值 n 0 为真。
归纳假设 。假设谓词对确定的 n ≥ n 0 为真。
归纳步骤 。证明如果 归纳假设 为真，则对于 n +1谓词也为真。
从而确定对于所有大于或等于 n 0 的值，谓词都为真。
• 乘积表示法用于表达一系列
因子
的乘积。例如，表达式
表示因子
的乘积，
i
值的范围从1到
k
。
• 约定零个因子的乘积是1。
• 归纳定义 ，也被称为 递归定义 ，是用基础实例和构造实例来定义一个元素序列。
Thue 序列 就是一个例子。
3.1 求下列表达式的闭式表达式，见式（3-3）。
3.2 用归纳法证明鸽笼原理（例3.19），用| Y |代替| X |进行归纳。
3.3 用归纳法证明扩展鸽笼原理（定理1.3和定理1.4）。
3.4
（a）使用∑表示对2的前
n
个奇数幂求和（即项为2
1
、2
3
等），并用归纳法证明其和是
。
（b）使用
表示2的前
n
个负整数的幂的乘积（即因子为2
-1
、2
-2
等），求乘积的值。
3.5 对于任意的 n ≥0，用归纳法证明
3.6 对于任意的 n ≥0，设
我们要证明 S （ n ）总是小于2的，且当 n 足够大时，它趋近于2。
（a） S （0）、 S （1）、 S （2）、 S （3）都等于什么？
（b）推测 S （ n ）的通用公式，形式如下：
S ( n )=2-…
（c）用归纳法证明，该公式对于所有的 n ≥0都是正确的。
（d）设 ε 是一个非常小的正实数。 n 为多大时， S （ n ）可以达到2的 ε 邻域内？
3.7 对于任意的 n ≥0，用归纳法证明
3.8 对于任意的 n ≥1，用归纳法证明
3.9 指出下面证明中的漏洞。
所有的马都是相同的颜色 。
归纳基础 。考虑只有一匹马的集合。只有一匹马意味着这匹马和它自己是同样颜色的，所以命题成立。
归纳假设 。假设对于所有 n ≥1的马的集合，所有的马都是相同的颜色。
归纳步骤 。证明“对于所有 n +1匹马的集合，在同一个集合中的所有马都是相同的颜色”，设一个有 n +1匹马的集合如下：
H ={ h 1 , h 2 ,…, h n , h n+ 1 }
设 H 有两个不同的子集：
A ={ h 1 , h 2 ,…, h n }
B ={ h 2 ,…, h n , h n+ 1 }
由于 A 和 B 都是 n 个元素的集合，所以在每个集合中，所有马都是相同颜色的。由于 h n +1 与 h 2 的颜色相同（因为两者都在 B 集合中）， h 2 （也在 A 集合中）与 A 集合中的其他马是相同的颜色。因此， h n +1 和 A 集合中的所有马是相同的颜色，所以 H 集合中的所有马肯定都是相同的颜色。
因此，对于任意大小的马的集合，同一集合中的所有马都是相同的颜色。
3.10 如果相继两个元素之间的差每向后一步就会增加1，那么512真的会出现在求和公式（3-2）中最后一个数的位置上吗？
3.11 证明下面有关Thue序列的结论。
（a）对于任意的 n ≥1， T 2 n 是一个 回文字符串 （palindrome），即一个字符串正读和反读都是相同的。
（b）对于任意的 n ，如果同步将 T n 中的0换为01、1换为10，可得到 T n +1 。这意味着在无穷的Thue位串 t 0 t 1 …中，也会同步发生上述替换，那么还会得到一个无穷的Thue位串。
3.12 证明：数学归纳法原理比实际需要更通用。也就是说，数学归纳法能证明的命题，弱数学归纳法原理也可以证明：
如果 P (0) 为真，并且对于任意的 n ， 当 P ( n ) 为真时 ， P ( n +1) 为真，那么对于所有的 n ， 有 P ( n ) 为真 。
在数学归纳法中，当固定 n 0 的值为0时，我们称之为弱归纳法。
[1] 我们在公式中使用（2i+1）来表示项，括号的作用是避免歧义，即我们是对整个表达式求和，不是仅对其中的2 i 求和（见下式），此值与原式不相同。
