(涵盖第 4 个讲义)

LN4 Proof by Induction 科学归纳法

Ordinary Induction

证明对于任意 x ≥ n, P(x) Base case: 直接计算 P(n)，说明其正确 Induction step：假设 P(m)正确，推导 P(m+1)正确

例：证明柯西不等式(对于任意 a_i, b_i) $$a_{1}b_{1} + a_{2}b_{2} + \cdots + a_{n}b_{n} ;\leq; \sqrt{a_{1}^{2} + a_{2}^{2} + \cdots + a_{n}^{2}} ; \sqrt{b_{1}^{2} + b_{2}^{2} + \cdots + b_{n}^{2}}\ \ \ \ \ (n)$$ $$Proof:\ Base\ case:|a_1b_1| = \sqrt{a_1^2}\sqrt{b_1^2},\ \ so\ a_1b_1 ≤ \sqrt{a_1^2}\sqrt{b_1^2}\ \ \ \ \ (1)$$ $$Induction:Given\ (n),\ denote\ it\ as\ \ x≤pq,\ so:$$ $$x+a_{n+1}b_{n+1}≤pq+a_{n+1}b_{n+1}$$ $$Given\ (2),\ pq+a_{n+1}b_{n+1}≤\sqrt{p^2+a_{n+1}^2}\sqrt{q^2+b_{n+1}^2}\ \ \ \ \ (n+1)\ \ Q.E.D$$ (因为递归用到了两项成立的结论，需要额外证明两项时成立)

Strong Induction

证明对于任意 x ≥ n, P(x) Base case: 直接计算 P(n)，说明其正确 Induction step：假设 P(n)…P(m)全部正确，推导 P(m+1)正确

例：证明只用 3 和 5 的加法操作可以组成任意大于 8 的整数 列举：3+5=8，3+3+3=9，5+5=10 对于 n = 11，n-3 = 8，可以表示 …… 对于 n = m, n-k3 = 8 or 9 or 10，可以表示 (任意 n ≥ 11，n-k3 一定等于 8 或 9 或 10，只要再加 k 个 3 即可组成)

良序性 WOP

$ WOP：任意非空的自然数集合都有一个最小元素。 变形：任意非空正整数集合都有一个最小元素。

证明对于任意 x ∈ N, P(x) 假设 ¬P(x)，那么 S ::= {n ∈ N | ¬P(n)} 有良序性 找出最小项或最小项必须符合的性质，再通过这个性质推出更小项，产生矛盾

例 1：证明 √2 是无理数

Proof by Contradiction: Suppose √2 is natural, then it can be written as √2 = p / q, where p and q are natural numbers. Then, in the natural set of denominators p, there must be a least one (By WOP). $${p^2 \over{q^2}}=2,\ so\ smallest\ p\ should\ be\ a\ even\ number:\ p_0=2k, q_0=2l$$ $$4k^2=2\times 4l^2,\ but\ k={p_0\over 2}\ also\ hold,\ so\ p_0\ is\ NOT\ smallest.$$ there’s always a smaller denominator, thus the hypothesis is false.

例 2：证明方程 4a³+2b³=c³ 无正整数解

Suppose there is a Z⁺ solution for this function. then S::={a ∈ℤ⁺| ∃𝑏,𝑐∈ℤ+, 4a³+2b³=c³} must have a smallest element (By WOP). Denote smallest one as a₀, b₀, c₀. $$Since\ 4a^3\ and\ 2b^3\ are\ both\ even,\ c^3\ and\ hence\ c\ are\ even,\ denote\ c_0=2p$$ $$Thus,\ 4a^3+2b^3=(2p)^3 \to b^3=4p^3-2a^3,\ hence\ b^3\ and\ b\ are\ even,\ denote\ b_0=2q$$ $$a^3=2p^3-4q^3, then\ a_0,b_0\ and\ c_0\ are\ all\ even$$ $$However,\ ({a\over 2},{b\over 2},{c\over 2})\ also\ must\in S, thus\ hypothesis\ is\ false.$$

不变量法 Invariant Method

对于一列整数(一到一百)，每次随机拿走两个数，并加入这两个数的平方和，最终剩下的数大小固定吗？是奇数还是偶数？

思路：“总奇偶性”是不变量。 大小不固定，因为返回的平方和也有几率被再次选中。但不管拿走哪两个数，其的平方和的奇偶性永远等于它们的和的奇偶性。所以最后的奇偶性等于原本所有数的和的奇偶性(偶数)。

思考题

猜想： 设左边为初始状态(也就是偶排列)，把排列奇偶性(即从初始状态需要多少次才能推出)记作 a，假设从下到上、从右到左每一行分别为 1-4 行，yOx。把奇数记作 1，偶数记作 0。空格奇偶性为 x⊕y：

总奇偶性为 (x⊕y)⊕a，初始状态为 0⊕0⊕0=0。 以空格为对象，空格向上交换一次：1⊕0⊕1=0，再向左交换一次：1⊕1⊕0=0… 无论如何， 运算结果一定是 0，但右侧是奇数排序：0⊕0⊕1=1，所以不可能。

• CSC3001