อุปนัยแบบเข้ม (Strong Induction): หลักการ จำนวนกรณีฐาน ตัวอย่างเข้มข้น 17 ข้อ และแล็บฝึกพิสูจน์

1. ข้อความ $P(n)$: มีจำนวนเต็ม $x, y \ge 0$ ที่ $n = 3x + 5y$

2. ดูขั้นอุปนัย: จะได้ $n$ จาก $n - 3$ แล้วเติมแสตมป์ 3 บาท ⇒ ย้อน 3 ขั้น ⇒ ต้องมีกรณีฐาน 3 ตัว

3. กรณีฐาน: $8 = 3 + 5$, $9 = 3 + 3 + 3$, $10 = 5 + 5$

4. สมมติฐานแบบเข้ม: ให้ $n \ge 11$ และ $P(j)$ จริงทุก $8 \le j < n$ เพราะ $8 \le n - 3 < n$ จึงมี $\hlP{n - 3 = 3x + 5y}$

5. $n = 3(x + 1) + 5y$ ⇒ $P(n)$ จริง ∎

ราคาที่รวมไม่ได้มีเพียง 1, 2, 4, 7 (สี่ค่า $= \tfrac{2\cdot4}{2}$) และ $7 = 3\cdot5 - 3 - 5$

1. $g(4, 7) = 28 - 4 - 7 = 17$ ราคาที่รวมไม่ได้: 1, 2, 3, 5, 6, 9, 10, 13, 17 (เก้าค่า $= \tfrac{3\cdot6}{2}$)

2. ขั้นอุปนัยเติมแสตมป์ 4 บาท ⇒ กรณีฐาน 4 ตัว: $18 = 4 + 7 + 7$, $19 = 4\cdot3 + 7$, $20 = 4\cdot5$, $21 = 7\cdot3$

3. ให้ $n \ge 22$ และสมมติ $P(j)$ ทุก $18 \le j < n$ เพราะ $n - 4 \ge 18$ จึงมี $\hlP{P(n-4)}$ เติม 4 บาทได้ $P(n)$ ∎

รวมได้ทุก $n \ge 18$ เปิดในแล็บ

1. กรณีฐาน $n = 2$ เป็นจำนวนเฉพาะ (ผลคูณของจำนวนเฉพาะหนึ่งตัว)

2. สมมติฐานแบบเข้ม: ให้ $n \ge 3$ และทุก $2 \le j < n$ เป็นผลคูณของจำนวนเฉพาะ

3. ถ้า n เป็นจำนวนเฉพาะ จบทันที ถ้าไม่ใช่ $n = ab$ โดย $2 \le a, b \le n/2 < n$ จึงใช้ $\hlP{P(a),\ P(b)}$ ได้

4. นำผลคูณจำนวนเฉพาะของ a กับ b มาต่อกันเป็นของ n ∎

กรณีฐานมีตัวเดียว แม้ขั้นอุปนัยกระโดดไกล เพราะ a, b ≥ 2 อยู่ในโดเมนเสมอ

1. กรณีฐาน $n = 1 = 2^0$

2. ให้ $n \ge 2$ และสมมติ $P(j)$ ทุก $1 \le j < n$ เขียน $n = 2m + b$ โดย $b \in \{0, 1\}$ และ $1 \le m = \lfloor n/2\rfloor < n$

3. จาก $\hlP{P(m)}$: $m = \sum 2^{e_i}$ (e ต่างกัน) ⇒ $2m = \sum 2^{e_i + 1}$ ไม่มีพจน์ $2^0$ จึงบวก $b\cdot 2^0$ ได้โดยไม่ซ้ำ ∎

นี่คือการหารสองซ้ำ ๆ แปลงเลขฐานสิบเป็นฐานสอง ดูในแล็บ (45)

1. กรณีฐาน (สองตัวเพราะย้อนสองขั้น): $F_1 = 1 < 2,\ F_2 = 1 < 4$

2. ให้ $n \ge 3$ และ $P(j)$ ทุก $1 \le j < n$: $F_n = \hlP{F_{n-1}} + \hlP{F_{n-2}} < 2^{n-1} + 2^{n-2} = 3\cdot2^{n-2} < 4\cdot 2^{n-2} = 2^n$ ∎

ฐาน 2 “หลวม” มาก ฐานที่เล็กที่สุดที่ใช้ได้คือ $\varphi \approx 1.618$ ลองเลื่อนแถบในแล็บด้านล่างให้ r ต่ำกว่า φ แล้วดูขั้นอุปนัยพัง

1. กรณีฐาน: $F_1 = 1 \ge \varphi^{-1} \approx 0.618$ และ $F_2 = 1 \ge \varphi^0 = 1$

2. $F_n = F_{n-1} + F_{n-2} \ge \varphi^{n-3} + \varphi^{n-4} = \varphi^{n-4}(\varphi + 1) = \varphi^{n-4}\cdot\varphi^2 = \varphi^{n-2}$ ∎

ใช้ $\varphi^2 = \varphi + 1$ เป็นกุญแจ ผลนี้ทำให้รู้ว่าอัลกอริทึมยุคลิดใช้จำนวนรอบเป็นลอการิทึม (ทฤษฎีบทของลาเม)

1. กรณีฐาน: $2 - 1 = 1 = a_1$, $4 + 1 = 5 = a_2$ ✓

2. ให้ $n \ge 3$ และสมมติสูตรจริงสำหรับ $n - 1$ และ $n - 2$:

   $$\begin{aligned} a_n &= \hlP{2^{n-1} + (-1)^{n-1}} + 2\big(\hlP{2^{n-2} + (-1)^{n-2}}\big) \\ &= 2^{n-1} + 2^{n-1} + (-1)^{n-2}(-1 + 2) \\ &= 2^n + (-1)^n \end{aligned}$$

สูตรมาจากสมการลักษณะเฉพาะ $t^2 = t + 2$ ราก 2 และ −1 ให้เครื่องแก้สร้างบทพิสูจน์

1. ย้อน 3 ขั้น ⇒ กรณีฐาน 3 ตัว: $1 < 2,\ 1 < 4,\ 1 < 8$

2. ให้ $n \ge 4$: $T_n < 2^{n-1} + 2^{n-2} + 2^{n-3} = 7\cdot2^{n-3} < 8\cdot 2^{n-3} = 2^n$ ∎

ลำดับจริง 1, 1, 1, 3, 5, 9, 17, 31, 57, … โตด้วยฐานราว 1.839

1. กรณีฐาน: $n = 0$ ได้ $0$ และ $n = 1$ ได้ $\tfrac{\varphi - \psi}{\sqrt5} = \tfrac{\sqrt5}{\sqrt5} = 1$

2. ให้ $n \ge 2$: $F_n = \dfrac{\varphi^{n-1} - \psi^{n-1}}{\sqrt5} + \dfrac{\varphi^{n-2} - \psi^{n-2}}{\sqrt5} = \dfrac{\varphi^{n-2}(\varphi + 1) - \psi^{n-2}(\psi + 1)}{\sqrt5}$

3. แทน $\varphi + 1 = \varphi^2,\ \psi + 1 = \psi^2$ ได้ $\dfrac{\varphi^n - \psi^n}{\sqrt5}$ ∎

เพราะ $|\psi| < 1$ จึงได้ $F_n$ = จำนวนเต็มที่ใกล้ $\varphi^n/\sqrt5$ ที่สุด

1. ให้ $P(k)$: แท่งที่มี k ช่อง (รูปใดก็ได้) ต้องหัก $k - 1$ ครั้งพอดี · กรณีฐาน $k = 1$: หัก 0 ครั้ง

2. ให้ $k \ge 2$ สมมติ $P(j)$ ทุก $j < k$ การหักครั้งแรกให้สองชิ้นขนาด $p, q$ โดย $p + q = k$ และ $1 \le p, q < k$

3. รวม $1 + \hlP{(p - 1)} + \hlP{(q - 1)} = k - 1$ ∎ (มุมมองที่สั้นกว่า: หักหนึ่งครั้งเพิ่มชิ้นหนึ่งชิ้นเสมอ)

$mn - 1$ ครั้ง ไม่ว่าจะหักแบบไหน · แท่ง 3 × 4 ใช้ 11 ครั้ง

1. ดูชิ้นสุดท้ายทางขวา: เป็นโดมิโนตั้งหนึ่งชิ้น (เหลือ $2 \times (n-1)$) หรือโดมิโนนอนสองชิ้นซ้อนกัน (เหลือ $2 \times (n-2)$) ⇒ $T(n) = T(n-1) + T(n-2)$

2. กรณีฐาน $T(1) = 1,\ T(2) = 2$ จากนั้นอุปนัยแบบเข้มแสดงว่า $T(n) = F_{n+1}$ (เพราะทั้งสองข้างมีความสัมพันธ์และกรณีฐานเดียวกัน)

$T(5) = F_6 = 8$ แบบ ดูทั้งแปดแบบในแล็บ

1. กรณีฐาน $n = 1 = F$ · ให้ $n \ge 2$ และสมมติ $P(j)$ ทุก $j < n$

2. ถ้า n เป็นเลขฟีโบนัชชีจบทันที มิฉะนั้นให้ $F_k$ ใหญ่สุดที่ $F_k < n < F_{k+1}$ และ $r = n - F_k$

3. $r < F_{k+1} - F_k = F_{k-1}$ และ $r < n$ ⇒ $\hlP{P(r)}$ ให้ผลบวกของเลขฟีโบนัชชีที่ไม่ติดกันซึ่งทุกตัวเล็กกว่า $F_{k-1}$ จึงไม่ติดกับ $F_k$ ∎

$100 = 89 + 8 + 3$ ดูในแล็บ

1. $P(n)$: ตำแหน่ง n แพ้ (สำหรับคนที่ต้องเดิน) ⇔ $4 \mid n$ · กรณีฐาน $n = 0$: ไม่มีให้หยิบ แพ้ และ $4 \mid 0$ ✓

2. ให้ $n \ge 1$ และสมมติ $P(j)$ ทุก $j < n$ ถ้า $4 \mid n$: ทุกการหยิบได้ $n - 1, n - 2, n - 3$ ซึ่งหาร 4 ไม่ลงตัว จึงเป็นตำแหน่งชนะตาม $\hlP{P(n-1)}$, $\hlP{P(n-2)}$, $\hlP{P(n-3)}$ ⇒ n แพ้

3. ถ้า $4 \nmid n$: หยิบ $n \bmod 4$ อันไปที่พหุคูณของ 4 ซึ่งแพ้ตามสมมติฐาน ⇒ n ชนะ ∎

กลยุทธ์: ทิ้งพหุคูณของ 4 ให้คู่แข่งเสมอ ลองชนะคอมพิวเตอร์ในแล็บ

1. กรณีฐาน $T(1) = 0 \le 1\cdot 0$ · ให้ $n \ge 2$ และ $c = \lceil\log_2 n\rceil$ จึงมี $n \le 2^c$

2. $\lceil n/2\rceil \le 2^{c-1}$ ⇒ ทั้งสองครึ่งมี $\lceil\log_2(\cdot)\rceil \le c - 1$ และเล็กกว่า n จึงใช้ $\hlP{\text{สมมติฐานแบบเข้ม}}$ ได้

3. $T(n) \le \lfloor\tfrac n2\rfloor(c-1) + \lceil\tfrac n2\rceil(c-1) + n = n(c - 1) + n = nc$ ∎

merge sort ใช้การเปรียบเทียบ $O(n\log n)$ · อุปนัยธรรมดาบน $n - 1$ ใช้ไม่ได้เพราะการเรียกซ้ำกระโดดไปที่ $n/2$

1. กรณีฐาน $C(1) = 1 = 0 + 1$ · ให้ $n \ge 2$ สมมติสูตรจริงทุก $j < n$ โดยเฉพาะ $j = \lfloor n/2\rfloor$

2. ถ้า $2^m \le n < 2^{m+1}$ แล้ว $2^{m-1} \le \lfloor n/2\rfloor < 2^m$ ⇒ $\lfloor\log_2\lfloor n/2\rfloor\rfloor = m - 1$

3. $C(n) = 1 + \hlP{(m - 1) + 1} = m + 1 = \lfloor\log_2 n\rfloor + 1$ ∎

ค้นข้อมูลล้านรายการ (เรียงแล้ว) ใช้ไม่เกิน 20 รอบ

1. อุปนัยแบบเข้มบน b · กรณีฐาน $b = 0$: $\gcd(a, 0) = a = a\cdot1 + 0\cdot0$

2. ให้ $b \ge 1$: $a = qb + r$ โดย $0 \le r < b$ และ $\gcd(a, b) = \gcd(b, r)$ จาก $\hlP{P(r)}$ (เพราะ $r < b$): $\gcd(b, r) = bx' + ry'$

3. แทน $r = a - qb$: $\gcd(a,b) = ay' + b(x' - qy')$ ∎ (นี่คืออัลกอริทึมยุคลิดแบบขยาย)

4. $252 = 1\cdot198 + 54,\ 198 = 3\cdot54 + 36,\ 54 = 1\cdot36 + 18,\ 36 = 2\cdot18$ ย้อนกลับได้ $18 = 252\cdot4 - 198\cdot5$

$\gcd(252, 198) = 18 = 4(252) - 5(198)$ · r เป็นค่าใดก็ได้ที่น้อยกว่า b จึงต้องใช้อุปนัยแบบเข้ม

1. สัมประสิทธิ์ไม่ติดลบ ใช้ N7 กับ $r = 0.86$: $\tfrac{0.5}{0.86} + \tfrac{0.3}{0.86^2} = 0.5814 + 0.4056 = 0.9870 \le 1$ ✓ (ราก $t^2 = 0.5t + 0.3$ คือ 0.8521 จึงเลือก r ต่ำกว่า 0.8521 ไม่ได้)

2. กรณีฐานสองตัว: ต้องการ $C \ge e_0 = 1$ และ $C \ge e_1/0.86 = 1.1628$ ⇒ เลือก $C = 1.1628$

3. ขั้นอุปนัยแบบเข้ม: $e_n \le 0.5\,\hlP{Cr^{n-1}} + 0.3\,\hlP{Cr^{n-2}} = Cr^n\left(\tfrac{0.5}{r} + \tfrac{0.3}{r^2}\right) \le Cr^n$ ∎

ความคลาดลดลงอย่างน้อยแบบเรขาคณิตด้วยอัตรา 0.86 ต่อรอบ: หลัง 30 รอบเหลือไม่เกิน $1.1628(0.86)^{30} \approx 0.013$