Exercise 4.4-12

[Spdwal]

Describe the fallacy in the following “proof” by induction:

Statement. Given any collection of $n$ blonde girls. If at least one of the girls has blue eyes, then all $n$ of them have blue eyes.

“Proof.” The statement is obviously true when $n = 1$. The step from $k$ to $k + 1$ can be illustrated by going from $n = 3$ to $n = 4$. Assume, therefore, that the statement is true when $n = 3$ and let $G{1}$, $G{2}$, $G{3}$, $G{4}$, be four blonde girls, at least one of which, say $G{1}$ , has blue eyes. Taking $G{1}$, $G{2}$, and $G{3}$, together and using the fact that the statement is true when $n = 3$, we find that $G{2}$ and $G{3}$, also have blue eyes. Repeating the process with $G{2}$, $G{3}$ and $G{4}$, we find that $G{4}$, has blue eyes. Thus all four have blue eyes. A similar argument allows us to make the step from $k$ to $k + 1$ in general.

Corollary. All blonde girls have blue eyes.

Proof. Since there exists at least one blonde girl with blue eyes, we can apply the foregoing result to the collection consisting of all blonde girls.

Note: This example is from G. Pólya, who suggests that the reader may want to test the validity of the statement by experiment.

[muzimuzhi]

A similar argument allows us to make the step from $k$ to $k+1$ in general.

This statement is not true when $k = 1$. Hence, in general, the statement is false (since the counterexample exists when $k = 1$)

Following the method of proof by induction, if $A(n_1)$ is true, the second step requires that for arbitrary $k \ge n_1$, $A(k) \Longrightarrow A(k+1)$ holds. So in general, prove $A(c) \Longrightarrow A(c+1)$ for some constant integer $c$ (the wrong "proof" uses $c = 3$) is not sufficient.

[muzimuzhi]

More words.

• In step 1, we have $A(1)$ is true.
• The step 2 needs to prove $A(1) \Longrightarrow A(2)$, $A(2) \Longrightarrow A(3)$, $A(3) \Longrightarrow A(4)$, ... .
  • Firstly, the original proof explicitly proves $A(3) \Longrightarrow A(4)$.
  • And, this method does hold for every $A(k) \Longrightarrow A(k)$ ($k \ge 2$).
  • But it fails on $A(1) \Longrightarrow A(2)$. In text, given two girls, if one and only one has blue eyes, then both of them have blue eyes.
• Therefore the step 2 is invalid, and the whole "proof by induction" is invalid.

[muzimuzhi]

用中文解释下

原命题：任意 n 个女孩，如果至少有一个女孩满足条件 X，则所有女孩满足条件 X

原命题的加强（把「至少」去掉了）：任意 n 个女孩，如果有且只有一个女孩满足条件 X，则所有女孩满足条件 X

题干里证明的是这个加强的命题

---

题干里的证明

• n = 1 时，成立
• 如果 n = 3 成立，那么 n = 4 成立
• 这能推广到所有的 n >= 1（错在这里）

为什么错了呢？因为用题干里的方法，没法证明「如果 n = 1 成立，那么 n = 2 成立」

---

为什么没法证明「如果 n = 1 成立，那么 n = 2 成立」呢？

先看题干里的方法，证明 n = k 可以推到 n = k+1

• 用的条件是「k 个女孩，如果有一个满足条件 X，那么她们都满足」
• 约定标记方式： k+1 个女孩为 a1, …, a{k+1}，且只有 a_1 满足条件 X
• 找包含 a_1 的 k 个女孩，运用条件，那么这 k 个女孩就都满足条件 X
• 这样就相当于「条件 X」有传染性，所有 k+1 个女孩就都满足条件了

n = 1 推到 n = 2 会失败，是因为

• 「找包含 a_1 的 k 个女孩」这里，k = 1，只找到了一个女孩，条件 X 永远不会有「传染性」

[muzimuzhi]

所以，在英文的第一条回复里，我圈出来

A similar argument allows us to make the step from k to k+1 in general.

这句话是错的，错在 k = 1 时不成立。相当于有个边界情况没覆盖。

[muzimuzhi]

一个正常的证明结构，应当是

• n = 1，成立
• 假设 n = k 成立，下面推出 n = k + 1 时也成立
  • k = 1 时，balabala，推出 n = 2 时也成立
  • k >= 2 时，balabala，推出 n = k + 1 时也成立

综上，对任意正整数都成立

---

题干的问题是，其实那个方法只适用于 k >= 2 的情况，不适用于 k = 1 的情况，然而它用

A similar argument allows us to make the step from k to k+1 in general.

这句话糊弄过去了。