DIS01AB

1. 完全平方数

1. 1. 证明如果\(n^2\)是奇数，那么\(n\)也一定是奇数。
2. 2. 证明如果\(n^2\)是奇数，那么\(n^2\)可以写成\(8k + 1\)的形式，其中\(k\)为某个整数。

解决方案：

1. 1. 我们将通过反证法进行证明；该陈述的逆否命题是“如果\(n\)是偶数，那么\(n^2\)也是偶数”。在这里，因为\(n\)是偶数，我们可以写成\(n = 2k\)，其中\(k\)为某个整数。这使得\(n^2=(2k)^2 = 4k^2 = 2(2k^2)\)，这是偶数，如我们所愿。通过反证法，这意味着如果\(n^2\)是奇数，那么\(n\)一定也是奇数。
2. 2. 我们将进行直接证明。根据上一部分，因为\(n^2\)是奇数，\(n\)也是奇数，即\(n = 2l + 1\)，其中\(l\)为某个整数。然后，\(n^2 = 4l^2 + 4l + 1 = 4l(l + 1)+1\)。因为\(l\)和\(l + 1\)中必有一个是偶数，\(l(l + 1)\)的形式为\(2k\)，其中\(k\)为某个整数，所以\(n^2 = 8k + 1\)。

2. 朋友数量

证明如果派对上有\(n\geq2\)个人，那么至少有两个人在派对上的朋友数量相同。假设友谊总是相互的：也就是说，如果爱丽丝是鲍勃的朋友，那么鲍勃也是爱丽丝的朋友。

（提示：鸽巢原理指出，如果\(n\)个物品被放置在\(m\)个容器中，其中\(n>m\)，那么至少有一个容器必须包含不止一个物品。你可以直接使用这个原理而无需证明。）

解决方案：

​ 我们将通过反证法证明这一点。假设相反的情况，即每个人在派对上的朋友数量都不同。因为每个人可能拥有的朋友数量范围从\(0\)到\(n - 1\)，我们得出对于每个\(i\in\{0,1,\cdots,n - 1\}\)，在派对上恰好有一个人有\(i\)个朋友。特别地，有一个人有\(n - 1\)个朋友（即与每个人都是朋友），却与一个有\(0\)个朋友（即与任何人都不是朋友）的人是朋友。这是一个矛盾，因为友谊是相互的。 ​在这里，我们使用了鸽巢原理，因为假设每个人的朋友数量都不同会产生\(n\)个可能的容器。每个容器表示一个人拥有的朋友数量，所以容器可以标记为\(0,1,\cdots,n - 1\)。分配到这些容器中的对象是派对上的人。然而，容器\(0\)、\(n - 1\)或两者都必须是空的，因为这两个容器不能同时被占用。这意味着我们将\(n\)个人分配到最多\(n - 1\)个容器中，根据鸽巢原理，\(n - 1\)个容器中至少有一个必须有两个或更多的对象，即至少有两个人必须有相同数量的朋友。

3. 鹅卵石

假设你有一个长方形的鹅卵石阵列，其中每个鹅卵石要么是红色要么是蓝色。假设对于从每列中选择一个鹅卵石的每种方式，所选的鹅卵石中都存在一个红色鹅卵石。证明一定存在一整列都是红色鹅卵石。

解决方案：我们通过反证法进行证明；逆否命题是“如果不存在一整列都是红色鹅卵石，那么总是存在一种从每列中选择一个鹅卵石的方式，使得所选的鹅卵石中不存在红色鹅卵石”。

​ 假设不存在一整列都是红色鹅卵石。这意味着我们在每列中总是可以找到一个蓝色鹅卵石。因此，如果我们从每列中取一个蓝色鹅卵石，我们就有一种从每列中选择一个鹅卵石的方式，其中没有红色鹅卵石。这是原始假设的否定，所以我们完成了证明。 ​ 我们也可以通过矛盾法来解决这个问题；逻辑几乎完全相同，我们从结论的否定开始：即不存在一整列都是红色鹅卵石。上述相同的推理使我们得出结论，总是存在一种从每列中选择一个鹅卵石的方式，使得所有鹅卵石都是蓝色（即没有鹅卵石是红色）。

4. 不等式的自然归纳法

证明如果\(n\in\mathbb{N}\)且\(x > 0\)，那么\((1 + x)^n\geq1 + nx\)。

解决方案：

• 基础情形：当\(n = 0\)时，该断言成立，因为\((1 + x)^0\geq1 + 0\times x\)。
• 归纳假设：假设对于\(n = k\)（其中\(k\in\mathbb{N}\)），有\((1 + x)^k\geq1 + kx\)。
• 归纳步骤：对于\(n = k + 1\)，我们可以进行如下推导： \(\begin{align*}(1 + x)^{k + 1}&=(1 + x)^k(1 + x)\\&\geq(1 + kx)(1 + x)\\&\geq1 + kx + x + kx^2\\&\geq1 + (k + 1)x + kx^2\geq1 + (k + 1)x\end{align*}\) 通过归纳法，我们已经证明了对于所有\(n\in\mathbb{N}\)，\((1 + x)^n\geq1 + nx\)。

5. 加强证明

假设序列\(a_1,a_2,\cdots\)定义为\(a_1 = 1\)且\(a_{n + 1}=3a_n^2\)（对于\(n\geq1\)）。我们想要证明对于每个正整数\(n\)，\(a_n\leq3^{2^n}\)。

1. 1. 假设我们想要使用归纳法证明这个陈述。我们可以简单地让归纳假设为\(a_n\leq3^{2^n}\)吗？尝试用这个假设进行归纳证明，以说明为什么这行不通。
2. 2. 尝试使用归纳法证明陈述\(a_n\leq3^{2^n - 1}\)。
3. 3. 为什么(b)部分的假设意味着整体的断言？

解决方案：

1. 1. 让我们尝试通过归纳法证明对于每个\(n\geq1\)，有\(a_n\leq3^{2^n}\)。
   • 基础情形：对于\(n = 1\)，我们有\(a_1 = 1\leq3^{2^1}=9\)。
   • 归纳步骤：对于某个\(n\geq1\)，我们假设\(a_n\leq3^{2^n}\)。现在，考虑\(n + 1\)。我们可以写出： \(a_{n + 1}=3a_n^2\leq3(3^{2^n})^2=3\times3^{2\times2^n}=3\times3^{2^{n + 1}}=3^{2^{n + 1}+1}\) 然而，我们想要得到的是\(a_{n + 1}\leq3^{2^{n + 1}}\)这种形式的不等式。我们推导出来的结果在指数上多了一个\(+1\)。
2. 2. 这次归纳法可行。
   • 基础情形：对于\(n = 1\)，我们有\(a_1 = 1\leq3^{2 - 1}=3\)。
   • 归纳步骤：对于某个\(n\geq1\)，我们假设\(a_n\leq3^{2^n - 1}\)。现在，考虑\(n + 1\)。我们可以写出： \(a_{n + 1}=3a_n^2\leq3\times(3^{2^n - 1})^2=3\times3^{2\times(2^n - 1)}=3\times3^{2^{n + 1}-2}=3^{2^{n + 1}-1}\) 这正是\(n + 1\)时的归纳假设。
3. 3. 对于每个\(n\geq1\)，我们有\(2^n - 1\leq2^n\)，因此\(3^{2^n - 1}\leq3^{2^n}\)。这意味着我们在(b)部分证明的修改后的假设确实意味着我们在(a)部分想要证明的内容。

总结：当一个命题难以证明时，可以证明他的强化命题。从而证明原来的命题。

6. 二进制数

证明每个正整数\(n\)都可以用二进制表示。换句话说，证明对于任何正整数\(n\)，我们可以写成\(n = c_k\cdot2^k + c_{k - 1}\cdot2^{k - 1}+\cdots+c_1\cdot2^1 + c_0\cdot2^0\)，其中\(k\in\mathbb{N}\)且对于所有\(i\leq k\)，\(c_i\in\{0,1\}\)。

解决方案：

通过对\(n\)进行强归纳证明。 关键思路是，如果\(n\)能被\(2\)整除，那么很容易从\(n\)的二进制表示得到\((n + 1)\)的二进制表示。然而，如果\(n\)不能被\(2\)整除，那么\((n + 1)\)将能被\(2\)整除，并且它的二进制表示将更容易从\((n + 1)/2\)的二进制表示推导出来。更正式地：

• 基础情形：\(n = 1\)可以写成\(1\times2^0\)。
• 归纳步骤：假设对于所有\(1\leq m\leq n\)（其中\(n\)是任意的）该陈述为真。现在，我们需要考虑\(n + 1\)。如果\(n + 1\)能被\(2\)整除，那么我们可以将归纳假设应用于\((n + 1)/2\)，并使用其表示来将\(n + 1\)表示为所需的形式。 \(\begin{align*}(n + 1)/2&=c_k\cdot2^k + c_{k - 1}\cdot2^{k - 1}+\cdots+c_1\cdot2^1 + c_0\cdot2^0\\n + 1&=2\cdot(n + 1)/2=c_k\cdot2^{k + 1}+c_{k - 1}\cdot2^k+\cdots+c_1\cdot2^2 + c_0\cdot2^1 + 0\cdot2^0\end{align*}\) 否则，\(n\)必须能被\(2\)整除，因此有\(c_0 = 0\)。我们可以从\(n\)得到\(n + 1\)的表示如下： \(\begin{align*}n&=c_k\cdot2^k + c_{k - 1}\cdot2^{k - 1}+\cdots+c_1\cdot2^1 + 0\cdot2^0\\n + 1&=c_k\cdot2^k + c_{k - 1}\cdot2^{k - 1}+\cdots+c_1\cdot2^1 + 1\cdot2^0\end{align*}\) 因此，该陈述为真。 这里是另一种模仿将十进制数转换为二进制数算法的替代解决方案。
• 基础情形：\(n = 1\)可以写成\(1\times2^0\)。
• 归纳步骤：假设对于所有\(1\leq m\leq n\)（对于任意\(n\)）该陈述为真。我们证明该陈述对于\(n + 1\)成立。设\(2^m\)是\(2\)的最大幂次，使得\(n + 1\geq2^m\)。因此，\(n + 1 < 2^{m + 1}\)。我们检查数字\((n + 1)-2^m\)。由于\((n + 1)-2^m < n + 1\)，归纳假设成立，所以我们有\((n + 1)-2^m\)的二进制表示。（如果\((n + 1)-2^m = 0\)，那么我们仍然有一个二进制表示，即\(0\cdot2^0\)。） 此外，由于\(n + 1 < 2^{m + 1}\)，\((n + 1)-2^m < 2^m\)，所以\((n + 1)-2^m\)的二进制表示中\(2\)的最大幂次是\(2^{m - 1}\)。因此，根据归纳假设，\((n + 1)-2^m=c_{m - 1}\cdot2^{m - 1}+c_{m - 2}\cdot2^{m - 2}+\cdots+c_1\cdot2^1 + c_0\cdot2^0\)，两边加上\(2^m\)得到\(n + 1=2^m + c_{m - 1}\cdot2^{m - 1}+c_{m - 2}\cdot2^{m - 2}+\cdots+c_1\cdot2^1 + c_0\cdot2^0\)，这是\(n + 1\)的二进制表示。因此，归纳完成。 另一种直觉是，如果\(x\)有二进制表示，那么\(2x\)和\(2x + 1\)也有：移动位并可能在最后一位放置\(1\)。上述归纳可以从\(n\)开始，并使用\([n/2]\)的二进制表示，根据\(n\)是奇数还是偶数移动并可能设置第一位。 注意：在使用简单归纳法的证明中，我们仅使用\(P(n)\)来证明\(P(n + 1)\)。简单归纳法在这里遇到困难，因为为了在归纳步骤中证明\(P(n + 1)\)，我们需要假设的不仅仅是\(P(n)\)。这是因为不清楚如何仅使用\(P(n)\)来获得\(P(n + 1)\)的表示，特别是在\(n + 1\)能被\(2\)整除的情况下。因此，我们假设该陈述对于所有\(1,2,\cdots,n\)为真，以便证明它对于\(P(n + 1)\)成立。

7. 斐波那契数列

回想一下，斐波那契数列递归定义为\(F_1 = 1\)，\(F_2 = 1\)，且\(F_n = F_{n - 2}+F_{n - 1}\)。证明每个第三个斐波那契数是偶数。例如，\(F_3 = 2\)是偶数，\(F_6 = 8\)是偶数。

解决方案：

我们想要证明对于所有自然数\(k\geq1\)，\(F_{3k}\)是偶数。

• 基础情形：对于\(k = 1\)，我们可以看到\(F_3 = 2\)是偶数。
• 归纳假设：假设对于任意固定的\(k\)值，\(F_{3k}\)是偶数。
• 归纳步骤：我们可以写出\(F_{3k + 3}=F_{3k + 2}+F_{3k + 1}=2F_{3k + 1}+F_{3k}\)。 根据归纳假设，我们知道\(F_{3k}=2q\)（对于某个\(q\)）。 这意味着\(F_{3k + 3}=2(F_{3k + 1}+q)\)，这意味着它是偶数。因此，根据归纳原理，我们已经证明了所有\(F_{3k}\)都是偶数。