问题集2的解 到期：星期一，在2月4日的下午9点。使用归的证明： (-)(-)(-)(-)=日 对于所有的e2. 解：证明是由在n上的归钠法得到。令P()是的上述等式成立的命墨。 基例：P(2)为真，因为 归销步：假设P()为真，那么我们可以正明P(叶)也为真。如下 (-(-)(-(-+)=(-+) n+1 第一步使用假定P(,并且第二是化简。 因此，P(2)为真和P(n莲涵P(叶1).对于所有得n≥2，所以，P(为真。对所有n≥ 2,由归销法原理得。 问题2 DeMorgan定律说： An (BUCE(AnB)U (AnC) 假设这个为真，证明DeMorgar定律对n≥2集合扩展： An(BUB2U...UB)=(AnB)U(An B2)U...U(AnB) 扩展公式到任意数量的项（如果是强制的》是一个普通的归纳法的应用： 解：我们门使用归纳法。令)是命题： An(BUB2U...UB)=(An B)U(An B2)U...U(An B) 对任何A和B,B民的集合。 PF文件使用"pdfFactory Pro”试用版本创建w.finsprint,n
问题集 2 的解 到期： 星期一，在 2 月 14 日的下午 9 点。 使用归纳证明： 对于所有的 n≥ 2。 解： 证明是由在 n 上的归纳法得到。 令 P (n)是的上述等式成立的命题。 基例： P (2)为真，因为 归纳步： 假设 P (n)为真。 那么我们可以证明 P (n+ 1)也为真，如下： 第一步使用假定 P (n)，并且第二是化简。 因此， P (2)为真和 P (n)蕴涵 P (n+ 1)，对于所有得 n≥ 2。 所以， P (n)为真，对所有 n≥ 2，由归纳法原理得。 问题 2 DeMorgan 定律说： A∩ (B∪C)= (A∩B)∪ (A∩C) 假设这个为真，证明 DeMorgan 定律对 n≥ 2 集合扩展： 扩展公式到任意数量的项（如果是强制的）是一个普通的归纳法的应用。 解：我们使用归纳法。令 P(n)是命题： 对任何 A 和 B1,…,Bn的集合。 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
基例：PH2)从DMn的原米的定理得米，有B=B:且C=B: 归纳步：假设小，我们旋按黑知下鞋导代+1： A(B JB2UBU...LB=A((B.UB)JBU...UB.) (AnU(AnBC.U(ACU.) -(A0B)U(AC BU(ACBU...C(A8.) 在第一步中，我们把B,和B:放为一组。这个允许我们应用假设代)，在第二步，最后一步 使用xMan原来的定律。 因为2)为真，且o叶1)，对于所有的n≥2，对于自纳法原理暗示n)为真， 对于所有的n32. 问题3令H.表示第n个调和和，也就是定义为 Hn 调和和经常碰见。您将以后再看到它们，在6.042并且也在6.046. 断音H2m≥1+m/2,对于所有m0. ()下个问题部分将要求您用归纳法证明这个斯言。要使此更加容易。您可以发璞有三步 用在您的下面是列出的正明中。为这些步中的每一步提供一个句子料解。 2网+1 H2m+ k=1 2m+1 =H2m十 1 k=2m+1 1 H2m +2m. 2m+1 解：第一步使用H1的定义。第二步使用事实，前2严项的总和的与的所有2严项是 相等的。第三步使用事实，总和是由项的数量乘以最小项。 PDF文件使用“pdfFactory Pro”试用版本创建，fineprint.cn
基例：P(2) 从 DeMorgan 的原来的定理得来，有 B＝B1且 C＝B2。 归纳步：假设 P(n)，我们能按照如下推导 P(n+1)： 在第一步中，我们把 B1和 B2放为一组。这个允许我们应用假设 P(n)，在第二步。最后一步 使用 DeMorgan 原来的定律。 因为 P(2)为真，且 P(n)=>P(n+1)，对于所有的 n≥ 2，对于归纳法原理暗示 P(n)为真， 对于所有的 n≥ 2。 问题 3 令 Hn表示第 n 个调和和，也就是定义为： 调和和经常碰见。您将以后再看到它们，在 6.042 并且也在 6.046。 断言 ，对于所有 m≥0 。 (a) 下个问题部分将要求您用归纳法证明这个断言。 要使此更加容易，您可以发现有三步 用在您的下面是列出的证明中。 为这些步中的每一步提供一个句子辩解。 解： 第一步使用 H2m+1的定义。 第二步使用事实，前 2 m项的总和的与 H2m的所有 2 m项是 相等的。 第三步使用事实，总和是由项的数量乘以最小项。 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
)由归钠证明断言。（看到了吗？我们告诉了您这会发生的。） 解：我们通过归纳法证明断言，令P(m)是命题H≥1+m2, 基例：注意PO是为真，由于： H20=H1=121+0/2 归纳步：我们必领说明，P(m暗示P(m+1),对于所有m30。我们假设，P(m)为真 按照如下推理 2m+1 H2m+1三 k=1 2m+1 1 H2m+ k=2m+1 1 ≥H2m+2m. 2m+1 ≥(1+m/2)+1/2 =1+(m+1)/2 第一步使用H1的定文。第二步使用事实，前2m项的和与H的2m个项的和是相等的. 第三步使用事实。总和是以项的个数乘以最小项为下界的。第四步使用我们的假定代) 和化简。最后岁仅使用代数。这表示。P(m+I)为真，且，因此P(m)为真，对所有m 0,由归纳法得， (c表示，这蕴涵H,多1+12gn,当n是2的幂时。 解：这由不平等式，把n-lm带入断言得到. 问愿4假设我们想要划分口学生成为包含4名或5名学生的组。 (a)让我们使用强的归钠的会试证明，由≥8学生的班可以被划分成4或5个学生的小组. 证明：证明是由强的归纳法得到的。令P()是命题，由n个学生的班，可以被划分成4 成5个人的组。 基例：我们证明，P(为真，对n=8,9或者10，通过说明如何分解这些班的大小为4 名或5名学生的小组： Pf文件使用"pdfFactory Pro”试用版本创建ww.fineprint,n
(b)由归纳证明断言。 (看到了吗？ 我们告诉了您这会发生的。 ) 解：我们通过归纳法证明断言。 令 P (m)是命题 H2m ≥1+m/2。 基例：注意 P (0)是为真，由于： 归纳步： 我们必须说明， P (m)暗示 P (m +1)，对于所有 m≥ 0。 我们假设， P (m)为真 按照如下推理： 第一步使用 H2m+1的定义。第二步使用事实，前 2m 项的和与 H2m的 2m 个项的和是相等的。 第三步使用事实，总和是以项的个数乘以最小项为下界的。 第四步使用我们的假定 P(m) 和化简。 最后步仅使用代数。 这表示， P (m +1)为真，且，因此 P (m)为真，对所有 m ≥ 0，由归纳法得。 (c)表示，这蕴涵 Hn ≥ 1+1/2 log2 n，当 n 是 2 的幂时。 解：这由不平等式，把 n = log2 m 带入断言得到。 问题 4 假设我们想要划分 n 学生成为包含 4 名或 5 名学生的组。 (a)让我们使用强的归纳的尝试证明，由 n ≥ 8 学生的班可以被划分成 4 或 5 个学生的小组。 证明： 证明是由强的归纳法得到的。 令 P (n)是命题，由 n 个学生的班，可以被划分成 4 或 5 个人的组。 基例： 我们证明， P (n)为真，对 n = 8， 9 或者 10，通过说明如何分解这些班的大小为 4 名或 5 名学生的小组： PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
8=4+4 9 =4+5 10=5+5 归的步：我们必统说明P(8),",P(n)道锅P(+1)为所有n≥10。因此，我们假设，P (8),“,P()都为真。且说明如何划分叶1个学生的班成为4或5个学生的小组。我们 最初形成一个4名学生的小组。然后我们能划分剩余的广3学生到由4或5个学生的小组 里，由假定P(n-)得。这证明了P(叶1，且，因此由白纳法得断言成立。 这个证明包含一个重要逻辑错误。辨认在证明中第一个不成立的陈述，并解释出了什 么错。（指出断言是错的不是充足的：您必须发现在正明中的第一个泛辑错误。） 解：第一个情说在句子： 那么我们可以划分剩余的3学生成4暖5个学生的小组，由假定P(m3): 如果P10,那么P(-)-P(7),不是在我们的假定P(8,,P(n之中。在这种情况 下，P(叶1)=P(11)实际上是错误的。 (b提供正确强的白纳法证明，≥12学生的琉可以被划分成4或5个学生的小组。 解：正明是由强归纳法得米的。令P()是有n个学生的班可以被划分成有4吸5个学生的 组。 基例：我们证明，P)为真，对n=12.13.14和15，通过说明如何分解这些大小的 类为有4名或5名学生的小组： 12=4+4+4 13= 4+4+5 14=4+5+5 15=5+5+5 归销步：我们必须说明P(12),,P()酒涵P(5t1),对于所有n的≥1。因此，我 们假设，P(2),“,P)是全部为真，并且说明如何划分叶1学生的琉。我们最初形 成一个4名学生小组。然后我们可以划分剩余的n一3学生成4成5个学生的小组，由假 定P(伯-3).（注意到n≥15且因此312，因此，P(们3）是在我们的假设中，P (12),“,P(),之中)这证明P(叶1.且，因此由自纳法得断言成立， PF文件使用"pdfFactory Pro”试用版本创建w.finsprint,n
归纳步： 我们必须说明 P (8)，…， P (n)蕴涵 P (n+1)为所有 n≥ 10。 因此，我们假设， P (8)，…， P (n)都为真，且说明如何划分 n+1 个学生的班成为 4 或 5 个学生的小组。 我们 最初形成一个 4 名学生的小组。 然后我们能划分剩余的 n−3 学生到由 4 或 5 个学生的小组 里，由假定 P (n−3)得。 这证明了 P (n+ 1)，且，因此由归纳法得断言成立。 这个证明包含一个重要逻辑错误。 辨认在证明中第一个不成立的陈述，并解释出了什 么错。 (指出断言是错误的不是充足的; 您必须发现在证明中的第一个逻辑错误。) 解：第一个错误在句子： 那么我们可以划分剩余的 n− 3 学生成 4 或 5 个学生的小组，由假定 P (n− 3)。 如果 n= 10，那么 P (n−3) = P (7)，不是在我们的假定 P (8)，…， P (n) 之中。 在这种情况 下， P (n+ 1) = P (11)实际上是错误的。 (b)提供正确强的归纳法证明，n≥ 12 学生的班可以被划分成 4 或 5 个学生的小组。 解：证明是由强归纳法得来的。 令 P (n)是有 n 个学生的班可以被划分成有 4 或 5 个学生的 组。 基例： 我们证明， P (n)为真，对 n = 12， 13， 14 和 15，通过说明如何分解这些大小的 类为有 4 名或 5 名学生的小组： 归纳步： 我们必须说明 P (12)，…， P (n)蕴涵 P (5 n+ 1)，对于所有 n 的≥ 1。 因此，我 们假设， P (12)，…， P (n)是全部为真，并且说明如何划分 n+ 1 学生的班。 我们最初形 成一个 4 名学生小组。 然后我们可以划分剩余的 n − 3 学生成 4 或 5 个学生的小组，由假 定 P (n − 3)。 (注意到 n ≥ 15 且因此 n− 3 ≥ 12; 因此， P (n− 3)是在我们的假设中，P (12)，…， P (n)。之中) 这证明 P (n+ 1)，且，因此由归纳法得断言成立。 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
间题5如果正整数的一汇聚不一定不一样)有总和n≥1，则汇集有乘积至多式3“. 例如，汇集2.2,3.4,4,7有总和： 2+2+3+4+4+7=22 另一方面，乘积是： 2.2.3.4.4.7=1344 ≤ 322/3 ≈3154.2 包作为初始，使用强归纳法证明，对好个n≥0有整数有n≤3”/3 解：由强归钠法证明。令P()是n忘3的命题。 基例：我们表示，P0):P(I,P2,P(3)和P(4)是为真 03≤30→0≤3/3 13≤3 1≤31/8 23≤32 2≤32/3 33≤33 → 3≤33/8 48≤34-4≤3/8 每种涵义通过取立方根得到， 归销步，现在。我们说明P(O,,P(道涵P(叶1h对所有n≥的4。因此，我们假 设，PO),,P()为真，按照如下推理： 3n+1)/3 = 3.3n-2/3 ≥3.(n-2) ≥n+1 (for all n≥7/2) 第一步是代数。第二步使用我们的假定P们一2).第三步是为所有≥？2成立的线性不 PDF文件使用“pdfFactory Pro”试用版本创建fineprint.cn
问题 5 如果正整数的一汇聚(不一定不一样)有总和 n ≥ 1，则汇集有乘积至多式 3 n/3。 例如，汇集 2， 2， 3， 4， 4， 7 有总和： 另一方面，乘积是： (a)作为初始步，使用强归纳法证明，对每个 n≥ 0 得整数有 。 解：由强归纳法证明。 令 P (n)是 n ≤ 3n/3的命题。 . 基例： 我们表示， P (0)， P (1)， P (2)， P (3)和 P (4)是为真： 每种涵义通过取立方根得到。 归纳步： 现在，我们说明 P (0)，…， P (n)蕴涵 P (n+ 1)，对所有 n≥的 4。 因此，我们假 设， P (0)，…， P (n)为真，按照如下推理： 第一步是代数。 第二步使用我们的假定 P (n− 2)。 第三步是为所有 n≥ 7/2 成立的线性不 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
平等式（这迫使我们单鞋随处理P(3)和P(4的情况，上面。）所以，P(时1）是真实的，且， 因此由归纳法得，P(为真，对所有≥0。 ()使用归纳法或强白纳法证明断言。（您也许发现，在汇集上得正整数得个数上使用归钠 法是比在和n上容易的。) 解：我们使用在汇集的大小上的归纳法。令Pk)是有总和·的k个正整数的汇集的乘积至 多为3。首先，由前面的问题部分，注意到P(1)为真。 其次，我们经领说明，Pk)蕴钢Pk+1),对于所有的k≥1。因此假设。P(化为真，并 且令。：，。是有总和的正整数的一汇集。然后我们可以按照如下推理： 1·2…Ek41≤3n-+1/3.Ek+ 3n-k+1)/3.32k+1/3 3/3 第一步使用假定Pk),第二使用在先前的问题部分，并且最后步是代数。这说明，P化+) 是为真。且，因此由归纳法得斯言成立。 问题6假设您采取一素纸并且画n条直线，设有一条确切在另一条上面。完全在纸上交义。 这把纸划分成多边形区城。由归纳法证明您能在每个区域上色为红色或蓝色，以便分享边 界的不同区城总是着不同的氯色。（分享仅界限点的地区也许有同一种碳色。） 解：由归纳法证明。◆P(是能被条线划分的区城被看色为红色暖蓝色。以粳相邻的区 线着不同的颜色的命题。 基例：如果n0,那么没有线和整个纸是一个难一区域。着色为红色。因为没有t邻区 就，原邻区城平凡的是不月的顾色。因此，P(0)是真实的。 归销步：假设，P()是真实的。我们证明，Pn+1)也是真实的。给出时1线的配置， 去除一条任意线I。由假定P(),有利余的n条线定义的多边形区域能粮着色为红色或蓝 色，以便相邻的区城是着不同的碳色。现在把线ㄧ奉加回，且把每个区城的颜色反转到【 的一侧。在线的同一侧的相邻区域是由归纳法得到的不再的顾色。在线的相反侧的相邻的区 PF文件使用"pdfFactory Pro”试用版本创建ww.fineprint,n
平等式(这迫使我们单独地处理 P (3)和 P (4)的情况，上面。) 所以， P (n+ 1)是真实的，且， 因此由归纳法得，P (n)为真，对所有 n≥ 0。 (b) 使用归纳法或强归纳法证明断言。 (您也许发现，在汇集上得正整数得个数上使用归纳 法是比在和 n 上容易的。) 解：我们使用在汇集的大小上的归纳法。 令 P (k)是有总和 n 的 k 个正整数的汇集的乘积至 多为 3 n/3。 首先，由前面的问题部分，注意到 P (1)为真。 其次，我们必须说明， P (k)蕴涵 P (k+ 1)，对于所有的 k≥ 1。 因此假设， P (k)为真，并 且令 x1，…， xk+1是有总和 n 的正整数的一汇集。 然后我们可以按照如下推理： 第一步使用假定 P (k)，第二使用在先前的问题部分，并且最后步是代数。 这说明， P (k+ 1) 是为真，且，因此由归纳法得断言成立。 问题 6 假设您采取一张纸并且画 n 条直线，没有一条确切在另一条上面，完全在纸上交叉。 这把纸划分成多边形区域。 由归纳法证明您能在每个区域上色为红色或蓝色，以便分享边 界的不同区域总是着不同的颜色。 (分享仅界限点的地区也许有同一种颜色。) 解：由归纳法证明。 令 P (n)是能被 n 条线划分的区域被着色为红色或蓝色，以便相邻的区 域着不同的颜色的命题。 基例： 如果 n =0，那么没有线和整个纸是一个唯一区域。 着色为红色。 因为没有毗邻区 域，毗邻区域平凡的是不同的颜色。 因此， P (0)是真实的。 归纳步： 假设， P (n)是真实的。 我们证明， P (n + 1)也是真实的。 给出 n+ 1 线的配置， 去除一条任意线 l。 由假定 P (n)，有剩余的 n 条线定义的多边形区域能被着色为红色或蓝 色，以便相邻的区域是着不同的颜色。 现在把线 l 添加回，且把每个区域的颜色反转到 l 的一侧。在线的同一侧的相邻区域是由归纳法得到的不同的颜色。在线的相反侧的相邻的区 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
域是不同的颜色，因为在一侧的碳色反转了，因此代)道涵+1，且因此)为真，对于 多有的n≥0，由归纳法得。 问题7让我们考虑在演讲展示的拆堆静戏的变种。正如前面，玩家给出一个多1砖的 堆。通过移动序列，她必须使此降低到个单鞋的砖堆，当尽可能得许多分时。移动包括 划分堆(a+b)政其中：bO)成与a和b,段设这个移动值叶b分。发现最佳的战略并且 使用白纳证明。没有更好的战略。 解：一些实验建议最佳的战略是每次去除一个砖块。这给一个分数： n+(m-1)+..+3+2= n(n+1) 2 (n+2)(m-1) 2 联在我们门必须证明，设有更好的战略。 证明：我们使用强归纳法证明。令P()是拆n块砖的堆至多值叶2)1)2点的命题. 基例：P(1)为真，因为比赛立刻结束，当只有1块将。因此，玩家比分是0，（叶2）(r12, 当el. 归销步：现在假设P(),“,P)为真，为了证明P(,这里n≥2。假设n块砖的 堆被分裂成堆高度x和x,其中0x≤：为游戏的玩家的最好的可能的分数是 (m-x)+x+(x+2)(x-1)/2+(n-x+2(m-x-1)/2 for first move to unstack r bricks to unstack n -r bricks 这里我们使用假定P()和P(一)，其指定了最好可能的为了拆x和广×砖堆的分数。现 在我们必须选择x米最大化这个表达式。美于x的推理是2x一：因此，表达式减少。当 x从1增长到2，然后当x增加的时候，对将增加， 所以，当x1或x=1的时候，最大值达到。在两种情况下，上面的表达式等于： (n+2)(n-1)】 2 因此我门说明了P(I),,P(行1)涵P( 因此，P()为真。对所有n≥1。由强归纳法原则得。 PF文件使用"pdfFactory Pro”试用版本创建w.finsprint,n
域是不同的颜色，因为在一侧的颜色反转了。因此 P(n)蕴涵 P(n+1)，且因此 P(n)为真，对于 多有的 n≥ 0，由归纳法得。 问题 7 让我们考虑在演讲展示的拆堆游戏的变种。 正如前面，玩家给出一个 n≥ 1 砖的 堆。 通过移动序列，她必须使此降低到 n 个单独的砖堆，当尽可能得许多分时。 移动包括 划分堆(a+ b)砖(其中 a， b>0)成与 a 和 b。假设这个移动值 a+ b 分。 发现最佳的战略并且 使用归纳证明，没有更好的战略。 解： 一些实验建议最佳的战略是每次去除一个砖块。 这给一个分数： 现在我们必须证明，没有更好的战略。 证明： 我们使用强归纳法证明。令 P (n)是拆 n 块砖的堆至多值 (n+ 2) (n− 1)/2 点的命题。 基例：P (1)为真，因为比赛立刻结束，当只有 1 块砖。因此，玩家比分是 0，(n+ 2) (n− 1)/2， 当 n=1。 归纳步： 现在假设 P (1)，…， P (n− 1)为真，为了证明 P (n)， 这里 n≥ 2。假设 n 块砖的 堆被分裂成堆高度 x 和 n− x，其中 0<x< n。为游戏的玩家的最好的可能的分数是： 这里我们使用假定 P (x)和 P (n− x)，其指定了最好可能的为了拆 x 和 n− x 砖堆的分数。现 在我们必须选择 x 来最大化这个表达式。关于 x 的推理是 2x− n。 因此，表达式减少，当 x 从 1 增长到 n/2。然后当 x 增加的时候，对称增加。 所以，当 x =1 或 x = n− 1 的时候，最大值达到。在两种情况下，上面的表达式等于： 因此我们说明了 P (1)，…， P (n− 1)蕴涵 P (n)。 因此， P (n)为真，对所有 n≥ 1，由强归纳法原则得。 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn