--- title: "อุปนัยแบบเข้ม (Strong Induction): หลักการ จำนวนกรณีฐาน ตัวอย่างเข้มข้น 17 ข้อ และแล็บฝึกพิสูจน์" url: https://modsengineeringmath.com/learn/sequences-and-series/strong-induction/ site: "Mod's Engineering Mathematics (อาจารย์มด)" language: th updated: 2026-10-26 --- > อุปนัยเชิงคณิตศาสตร์แบบเข้ม (strong induction) ภาษาไทยแบบเจาะลึก: ต่างจากอุปนัยธรรมดาอย่างไร ต้องมีกรณีฐานกี่ตัว ตัวอย่าง 17 ข้อพร้อมวิธีทำ (แสตมป์ จำนวนเฉพาะ ฟีโบนัชชี ลำดับเวียนเกิด เกม merge sort ระบบควบคุม) และแล็บโต้ตอบ 11 ชุดให้ฝึกพิสูจน์บนมือถือ ฉบับ Markdown ของ https://modsengineeringmath.com/learn/sequences-and-series/strong-induction/ สำหรับผู้ช่วย AI และเครื่องมือค้นหา สูตรเขียนเป็น LaTeX ($…$ และ $$…$$) แล็บโต้ตอบและรูปมีเฉพาะในหน้าเว็บ # อุปนัยแบบเข้ม (Strong Induction): หลักการ จำนวนกรณีฐาน ตัวอย่างเข้มข้น 17 ข้อ และแล็บฝึกพิสูจน์ // บทที่ 26.12 · ลำดับและอนุกรม · Strong Induction อุปนัยธรรมดาบอกว่า “ถ้าตัวก่อนหน้าล้ม ตัวถัดไปล้ม” แต่โจทย์จริงจำนวนมากต้องการมากกว่านั้น: ฟีโบนัชชีต้องรู้สองตัวก่อนหน้า แสตมป์ 3 บาทย้อนกลับสามขั้น จำนวนเต็มแตกเป็นตัวประกอบที่เล็กกว่าเท่าไรก็ได้ อุปนัยแบบเข้มให้เราสมมติทุกกรณีที่เล็กกว่าพร้อมกัน หน้านี้พาฝึกตั้งแต่หลักการ การนับกรณีฐาน ไปจนถึงอัลกอริทึมและระบบควบคุม ด้วยตัวอย่าง 17 ข้อและแล็บที่ลองทำได้บนมือถือ ระดับพื้นฐาน ม.ปลาย · โอลิมปิกเบื้องต้นกลาง คณิตศาสตร์ไม่ต่อเนื่อง · แคลคูลัสขั้นสูง อัลกอริทึม · วิศวกรรม สรุปสั้นที่สุด - สมมติฐานแบบเข้ม: $P(j)$ จริงทุก $n_0 \le j \le n - 1$ แล้วพิสูจน์ $P(n)$ - จำนวนกรณีฐาน = จำนวนขั้นที่ย้อนกลับไกลที่สุด (ย้อน 2 ขั้น ต้องมี 2 กรณีฐาน) - ใช้เมื่อ P(n) อาศัย $P(n-2)$, $P(n-3)$, $P(\lfloor n/2\rfloor)$, ตัวประกอบของ n หรือ “ชิ้นที่เล็กกว่า” ที่ไม่รู้ขนาดล่วงหน้า - แล็บ 11 ชุด: กรณีฐาน · แสตมป์ · ต้นไม้ตัวประกอบ · ช็อกโกแลต · เกม · ฐานสอง/ฟีโบนัชชี · ปูกระเบื้อง · ขอบเขต · เวียนเกิด · เรียงบทพิสูจน์ · หาจุดผิด ## อุปนัยแบบเข้มคืออะไร ต่างจากอุปนัยธรรมดาอย่างไร พื้นฐาน นึกถึงแถวโดมิโน อุปนัยธรรมดา (weak / ordinary induction) รับประกันว่า “ตัวที่ k ล้มแล้วชนตัวที่ k + 1” ส่วนอุปนัยแบบเข้ม (strong / complete induction) รับประกันว่า “ถ้าตัวที่ $n_0$ ถึง $n - 1$ ล้มหมดแล้ว ตัวที่ n ก็ล้ม” เปรียบได้กับโดมิโนที่ต้องถูกชนจากหลายตัวพร้อมกัน หรือจากตัวที่อยู่ห่างออกไป N1 Principle of strong induction หลักอุปนัยแบบเข้ม $$\begin{gathered} P(n_0) \\ \wedge\ \Big[\forall n > n_0:\ \big(P(n_0) \wedge \dots \wedge P(n-1)\big) \Rightarrow P(n)\Big] \\ \Longrightarrow\ \forall n \ge n_0:\ P(n) \end{gathered}$$ ถ้าขั้นอุปนัยใช้ได้ตั้งแต่ $n \ge n_0 + b$ เท่านั้น ต้องพิสูจน์ $P(n_0), \dots, P(n_0 + b - 1)$ ตรง ๆ (กรณีฐาน b ตัว) N2 Equivalence อุปนัยธรรมดา ⇔ แบบเข้ม ⇔ หลักการจัดอันดับดี $$\begin{gathered} Q(n) := P(n_0) \wedge P(n_0 + 1) \wedge \dots \wedge P(n) \\ \text{แบบเข้มบน } P \ \equiv\ \text{แบบธรรมดาบน } Q \end{gathered}$$ หลักการจัดอันดับดี (well-ordering): เซตย่อยไม่ว่างของจำนวนนับมีสมาชิกน้อยที่สุดเสมอ ใช้พิสูจน์แบบ “สมมติมีตัวอย่างค้าน ให้ n เป็นตัวที่เล็กที่สุด” N3 How many base cases กฎจำนวนกรณีฐาน $$\begin{gathered} P(n) \Leftarrow P(n - s_1), \dots, P(n - s_m) \\ \Rightarrow\ \text{กรณีฐาน } \max_i s_i \text{ ตัวติดกัน} \end{gathered}$$ ถ้าย้อนแบบ $\lfloor n/2\rfloor$ หรือตัวประกอบ ต้องตรวจว่าทุกกรณีที่ย้อนไปยังอยู่ในโดเมน $\ge n_0$ แม่แบบเขียนพิสูจน์ด้วยอุปนัยแบบเข้ม 5 ขั้น - ข้อความ เขียน $P(n)$ ให้ชัด และบอกโดเมน $n \ge n_0$ - ดูขั้นอุปนัยก่อน ร่างว่าจะพิสูจน์ $P(n)$ จากกรณีใด ($n-1$? $n-2$? $n-3$? ตัวประกอบ?) เพื่อรู้ว่าต้องมีกรณีฐานกี่ตัว - กรณีฐาน ตรวจ $P(n_0), P(n_0+1), \dots$ ครบทุกตัวที่ขั้นอุปนัยยังใช้ไม่ได้ - สมมติฐานอุปนัยแบบเข้ม “ให้ $n \ge n_0 + b$ และสมมติว่า $P(j)$ จริงทุก $n_0 \le j < n$” - ขั้นอุปนัย + สรุป แสดง $P(n)$ โดยชี้ว่าใช้ $P(\cdot)$ ตัวใดและทำไมมันอยู่ในช่วงที่สมมติ แล้วสรุป “โดยหลักอุปนัยแบบเข้ม $P(n)$ จริงทุก $n \ge n_0$” ภาษาอังกฤษที่ใช้ในข้อสอบ: “Assume, as the strong inductive hypothesis, that $P(j)$ holds for all $n_0 \le j \le k$. We show $P(k+1)$.” · ทบทวนอุปนัยธรรมดาได้ที่ อุปนัยเชิงคณิตศาสตร์ (3.2) ## ต้องมีกรณีฐานกี่ตัว: ทดลองให้บทพิสูจน์พังเอง พื้นฐาน แล็บนี้แสดง P(n) ตั้งแต่ $n_0$ ถึง $n_0 + 29$ แต่ละช่องจะ “ล้ม” (เขียว) ได้ก็ต่อเมื่อกรณีที่มันอาศัยล้มหมดแล้ว แตะตัวเลขเพื่อดูว่ามันอาศัยใคร แล้วลองลดจำนวนกรณีฐานทีละหนึ่ง จะเห็นทันทีว่าช่องแรกที่ขาดหลักยึดอยู่ตรงไหน ลองแบบแบ่งครึ่ง ⌊n/2⌋ และแยกตัวประกอบด้วย: ขั้นอุปนัยกระโดดไกลมากแต่กรณีฐานกลับน้อย เพราะสิ่งที่สำคัญคือ “กรณีที่อ้างถึงถูกพิสูจน์ไปก่อนแล้วหรือยัง” ไม่ใช่ระยะห่าง กฎที่ใช้ในข้อสอบก่อนเขียนกรณีฐาน ให้ร่างขั้นอุปนัยเสมอ ถ้าขั้นอุปนัยใช้ $P(n-1)$ กับ $P(n-2)$ ขั้นอุปนัยนั้นใช้ได้ตั้งแต่ $n \ge n_0 + 2$ จึงต้องพิสูจน์ $P(n_0)$ และ $P(n_0+1)$ เอง ข้อสอบมักหักคะแนนเต็มขั้นถ้าขาดกรณีฐานตัวที่สอง ## กลุ่มที่ 1: แสตมป์และเหรียญ (ปัญหาโฟรเบเนียส) พื้นฐาน “มีแสตมป์ราคา a และ b บาท ราคาใดบ้างที่รวมได้พอดี” เป็นตัวอย่างคลาสสิกที่สุดของอุปนัยแบบเข้ม เพราะขั้นอุปนัย “เติมแสตมป์ดวงที่ถูกที่สุดอีกดวง” ย้อนกลับไปหลายขั้นพร้อมกัน N4 Frobenius number ราคาใหญ่สุดที่รวมไม่ได้ (สองชนิด) $$\begin{gathered} \gcd(a, b) = 1 \ \Rightarrow\ g(a, b) = ab - a - b \\ \#\{\text{ราคาที่รวมไม่ได้}\} = \frac{(a-1)(b-1)}{2} \end{gathered}$$ ทุกราคา $n > ab - a - b$ รวมได้ · ถ้า $\gcd(a,b) = d > 1$ จะรวมได้เฉพาะพหุคูณของ d ตัวอย่าง N-1 · กรณีฐานสามตัว ### แสดงว่าทุกราคา $n \ge 8$ บาท รวมได้พอดีด้วยแสตมป์ 3 และ 5 บาท - ข้อความ $P(n)$: มีจำนวนเต็ม $x, y \ge 0$ ที่ $n = 3x + 5y$ - ดูขั้นอุปนัย: จะได้ $n$ จาก $n - 3$ แล้วเติมแสตมป์ 3 บาท ⇒ ย้อน 3 ขั้น ⇒ ต้องมีกรณีฐาน 3 ตัว - กรณีฐาน: $8 = 3 + 5$, $9 = 3 + 3 + 3$, $10 = 5 + 5$ - สมมติฐานแบบเข้ม: ให้ $n \ge 11$ และ $P(j)$ จริงทุก $8 \le j < n$ เพราะ $8 \le n - 3 < n$ จึงมี ${n - 3 = 3x + 5y}$ - $n = 3(x + 1) + 5y$ ⇒ $P(n)$ จริง ∎ ราคาที่รวมไม่ได้มีเพียง 1, 2, 4, 7 (สี่ค่า $= \tfrac{2\cdot4}{2}$) และ $7 = 3\cdot5 - 3 - 5$ ตัวอย่าง N-2 · กรณีฐานสี่ตัว ### แสตมป์ 4 และ 7 บาท ราคาใดบ้างที่รวมไม่ได้ และพิสูจน์ว่าราคาตั้งแต่ 18 บาทขึ้นไปรวมได้หมด - $g(4, 7) = 28 - 4 - 7 = 17$ ราคาที่รวมไม่ได้: 1, 2, 3, 5, 6, 9, 10, 13, 17 (เก้าค่า $= \tfrac{3\cdot6}{2}$) - ขั้นอุปนัยเติมแสตมป์ 4 บาท ⇒ กรณีฐาน 4 ตัว: $18 = 4 + 7 + 7$, $19 = 4\cdot3 + 7$, $20 = 4\cdot5$, $21 = 7\cdot3$ - ให้ $n \ge 22$ และสมมติ $P(j)$ ทุก $18 \le j < n$ เพราะ $n - 4 \ge 18$ จึงมี ${P(n-4)}$ เติม 4 บาทได้ $P(n)$ ∎ รวมได้ทุก $n \ge 18$ ## กลุ่มที่ 2: จำนวนเฉพาะ การแยกตัวประกอบ และการเขียนเลขฐานสอง พื้นฐาน ตัวอย่างนี้แสดงเหตุผลที่อุปนัยธรรมดาไม่พอ: ถ้า $n = 360$ ไม่ใช่จำนวนเฉพาะ เราแตกเป็น $18 \times 20$ การรู้ว่า 359 เป็นผลคูณของจำนวนเฉพาะไม่ช่วยอะไร สิ่งที่ต้องการคือรู้เรื่องของ 18 และ 20 N5 Fundamental theorem of arithmetic ทฤษฎีบทหลักมูลของเลขคณิต $$n \ge 2\ \Rightarrow\ n = p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}$$ มีอยู่จริงและเขียนได้แบบเดียว (ไม่นับลำดับ) · ส่วน “มีอยู่จริง” พิสูจน์ด้วยอุปนัยแบบเข้ม ส่วน “แบบเดียว” ใช้บทตั้งของยุคลิด $p \mid ab \Rightarrow p \mid a \lor p \mid b$ ตัวอย่าง N-3 · ผลคูณจำนวนเฉพาะ ### พิสูจน์ว่าจำนวนเต็ม $n \ge 2$ ทุกตัวเขียนเป็นผลคูณของจำนวนเฉพาะได้ - กรณีฐาน $n = 2$ เป็นจำนวนเฉพาะ (ผลคูณของจำนวนเฉพาะหนึ่งตัว) - สมมติฐานแบบเข้ม: ให้ $n \ge 3$ และทุก $2 \le j < n$ เป็นผลคูณของจำนวนเฉพาะ - ถ้า n เป็นจำนวนเฉพาะ จบทันที ถ้าไม่ใช่ $n = ab$ โดย $2 \le a, b \le n/2 < n$ จึงใช้ ${P(a),\ P(b)}$ ได้ - นำผลคูณจำนวนเฉพาะของ a กับ b มาต่อกันเป็นของ n ∎ กรณีฐานมีตัวเดียว แม้ขั้นอุปนัยกระโดดไกล เพราะ a, b ≥ 2 อยู่ในโดเมนเสมอ ตัวอย่าง N-4 · เลขฐานสอง ### พิสูจน์ว่าจำนวนนับ n ทุกตัวเขียนเป็นผลบวกของกำลังของ 2 ที่ไม่ซ้ำกันได้ (มีเลขฐานสองเสมอ) - กรณีฐาน $n = 1 = 2^0$ - ให้ $n \ge 2$ และสมมติ $P(j)$ ทุก $1 \le j < n$ เขียน $n = 2m + b$ โดย $b \in \{0, 1\}$ และ $1 \le m = \lfloor n/2\rfloor < n$ - จาก ${P(m)}$: $m = \sum 2^{e_i}$ (e ต่างกัน) ⇒ $2m = \sum 2^{e_i + 1}$ ไม่มีพจน์ $2^0$ จึงบวก $b\cdot 2^0$ ได้โดยไม่ซ้ำ ∎ นี่คือการหารสองซ้ำ ๆ แปลงเลขฐานสิบเป็นฐานสอง ## กลุ่มที่ 3: ลำดับเวียนเกิด สูตรปิด และขอบเขต กลาง นี่คือกลุ่มที่พบบ่อยที่สุดในข้อสอบมหาวิทยาลัย ความสัมพันธ์ $a_n = c_1a_{n-1} + c_2a_{n-2}$ ย้อนสองขั้น จึงต้องใช้อุปนัยแบบเข้ม (หรืออุปนัยธรรมดาบนคู่ $(a_{n-1}, a_n)$) และกรณีฐานสองตัวเสมอ N6 Fibonacci bounds & Binet ขอบเขตและสูตรของบิเนต์ $$\begin{gathered} \varphi^{n-2} \le F_n \le \varphi^{n-1}\ (n \ge 1) \\ F_n = \frac{\varphi^n - \psi^n}{\sqrt5},\quad \varphi, \psi = \frac{1 \pm \sqrt5}{2} \end{gathered}$$ กุญแจของทุกข้อคือ $\varphi^2 = \varphi + 1$ (และ $\psi^2 = \psi + 1$) N7 Geometric bound ขอบเขต $a_n \le Cr^n$ ของเวียนเกิดสัมประสิทธิ์ไม่ติดลบ $$\begin{gathered} a_n = \sum_{i=1}^{k} c_i a_{n-i},\ c_i \ge 0 \\ \sum_{i=1}^{k} c_i r^{-i} \le 1,\quad a_{n_0+j} \le C r^{n_0+j}\ (j < k) \\ \Longrightarrow\ a_n \le C r^n \end{gathered}$$ r ที่เล็กที่สุดที่ใช้ได้คือรากบวกที่ใหญ่ที่สุดของสมการลักษณะเฉพาะ ตัวอย่าง N-5 · ขอบเขตบน ### $F_1 = F_2 = 1,\ F_n = F_{n-1} + F_{n-2}$ พิสูจน์ว่า $F_n < 2^n$ ทุก $n \ge 1$ - กรณีฐาน (สองตัวเพราะย้อนสองขั้น): $F_1 = 1 < 2,\ F_2 = 1 < 4$ - ให้ $n \ge 3$ และ $P(j)$ ทุก $1 \le j < n$: $F_n = {F_{n-1}} + {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 ต่ำกว่า φ แล้วดูขั้นอุปนัยพัง ตัวอย่าง N-6 · ขอบเขตล่างด้วย φ ### พิสูจน์ว่า $F_n \ge \varphi^{n-2}$ ทุก $n \ge 1$ เมื่อ $\varphi = \tfrac{1+\sqrt5}{2}$ - กรณีฐาน: $F_1 = 1 \ge \varphi^{-1} \approx 0.618$ และ $F_2 = 1 \ge \varphi^0 = 1$ - $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$ เป็นกุญแจ ผลนี้ทำให้รู้ว่าอัลกอริทึมยุคลิดใช้จำนวนรอบเป็นลอการิทึม (ทฤษฎีบทของลาเม) ตัวอย่าง N-7 · สูตรปิด ### $a_1 = 1,\ a_2 = 5,\ a_n = a_{n-1} + 2a_{n-2}$ พิสูจน์ว่า $a_n = 2^n + (-1)^n$ - กรณีฐาน: $2 - 1 = 1 = a_1$, $4 + 1 = 5 = a_2$ ✓ - ให้ $n \ge 3$ และสมมติสูตรจริงสำหรับ $n - 1$ และ $n - 2$: $$\begin{aligned} a_n &= {2^{n-1} + (-1)^{n-1}} + 2\big({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 ตัวอย่าง N-8 · กรณีฐานสามตัว ### $T_1 = T_2 = T_3 = 1,\ T_n = T_{n-1} + T_{n-2} + T_{n-3}$ พิสูจน์ว่า $T_n < 2^n$ - ย้อน 3 ขั้น ⇒ กรณีฐาน 3 ตัว: $1 < 2,\ 1 < 4,\ 1 < 8$ - ให้ $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 ตัวอย่าง N-9 · สูตรของบิเนต์ ### $F_0 = 0,\ F_1 = 1,\ F_n = F_{n-1} + F_{n-2}$ พิสูจน์ $F_n = \dfrac{\varphi^n - \psi^n}{\sqrt5}$ - กรณีฐาน: $n = 0$ ได้ $0$ และ $n = 1$ ได้ $\tfrac{\varphi - \psi}{\sqrt5} = \tfrac{\sqrt5}{\sqrt5} = 1$ - ให้ $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}$ - แทน $\varphi + 1 = \varphi^2,\ \psi + 1 = \psi^2$ ได้ $\dfrac{\varphi^n - \psi^n}{\sqrt5}$ ∎ เพราะ $|\psi| < 1$ จึงได้ $F_n$ = จำนวนเต็มที่ใกล้ $\varphi^n/\sqrt5$ ที่สุด ### เครื่องแก้ความสัมพันธ์เวียนเกิดที่เขียนบทพิสูจน์ให้ พิมพ์ความสัมพันธ์และค่าเริ่มต้น เครื่องมือหาสูตรปิดแบบแม่นตรง แล้วสร้างบทพิสูจน์ด้วยอุปนัยแบบเข้ม (กดเปิดส่วน “พิสูจน์สูตรด้วยอุปนัยแบบเข้ม” ท้ายผลลัพธ์) ใช้ตรวจว่าเราเขียนกรณีฐานครบและอ้างสมมติฐานถูกตัวหรือไม่ · รายละเอียดวิธีอยู่ที่ เครื่องคิดเลข 26.11 ## กลุ่มที่ 4: การนับและการแบ่งชิ้น กลาง เมื่อสิ่งของ “แตกเป็นสองชิ้นที่เล็กกว่า” โดยไม่รู้ว่าแต่ละชิ้นใหญ่เท่าไร อุปนัยแบบเข้มคือเครื่องมือธรรมชาติ ตัวอย่าง N-10 · ช็อกโกแลต ### แท่งช็อกโกแลต $m \times n$ หักได้ครั้งละหนึ่งชิ้นตามร่อง ต้องหักกี่ครั้งจึงได้ชิ้น $1 \times 1$ ทั้งหมด - ให้ $P(k)$: แท่งที่มี k ช่อง (รูปใดก็ได้) ต้องหัก $k - 1$ ครั้งพอดี · กรณีฐาน $k = 1$: หัก 0 ครั้ง - ให้ $k \ge 2$ สมมติ $P(j)$ ทุก $j < k$ การหักครั้งแรกให้สองชิ้นขนาด $p, q$ โดย $p + q = k$ และ $1 \le p, q < k$ - รวม $1 + {(p - 1)} + {(q - 1)} = k - 1$ ∎ (มุมมองที่สั้นกว่า: หักหนึ่งครั้งเพิ่มชิ้นหนึ่งชิ้นเสมอ) $mn - 1$ ครั้ง ไม่ว่าจะหักแบบไหน · แท่ง 3 × 4 ใช้ 11 ครั้ง ตัวอย่าง N-11 · ปูกระเบื้องโดมิโน ### กระดาน $2 \times n$ ปูด้วยโดมิโน $1 \times 2$ ได้กี่แบบ - ดูชิ้นสุดท้ายทางขวา: เป็นโดมิโนตั้งหนึ่งชิ้น (เหลือ $2 \times (n-1)$) หรือโดมิโนนอนสองชิ้นซ้อนกัน (เหลือ $2 \times (n-2)$) ⇒ $T(n) = T(n-1) + T(n-2)$ - กรณีฐาน $T(1) = 1,\ T(2) = 2$ จากนั้นอุปนัยแบบเข้มแสดงว่า $T(n) = F_{n+1}$ (เพราะทั้งสองข้างมีความสัมพันธ์และกรณีฐานเดียวกัน) $T(5) = F_6 = 8$ แบบ ดูทั้งแปดแบบในแล็บ ตัวอย่าง N-12 · ทฤษฎีบทเซกเคนดอร์ฟ ### พิสูจน์ว่าจำนวนนับทุกตัวเขียนเป็นผลบวกของเลขฟีโบนัชชี (1, 2, 3, 5, 8, …) ที่ไม่มีสองตัวใดติดกันในลำดับได้ - กรณีฐาน $n = 1 = F$ · ให้ $n \ge 2$ และสมมติ $P(j)$ ทุก $j < n$ - ถ้า n เป็นเลขฟีโบนัชชีจบทันที มิฉะนั้นให้ $F_k$ ใหญ่สุดที่ $F_k < n < F_{k+1}$ และ $r = n - F_k$ - $r < F_{k+1} - F_k = F_{k-1}$ และ $r < n$ ⇒ ${P(r)}$ ให้ผลบวกของเลขฟีโบนัชชีที่ไม่ติดกันซึ่งทุกตัวเล็กกว่า $F_{k-1}$ จึงไม่ติดกับ $F_k$ ∎ $100 = 89 + 8 + 3$ ## กลุ่มที่ 5: เกม อัลกอริทึม และระบบควบคุม ขั้นสูง ในวิทยาการคอมพิวเตอร์ อุปนัยแบบเข้มคือวิธีมาตรฐานในการพิสูจน์อัลกอริทึมแบบเรียกตัวเอง (recursive) เพราะการเรียกซ้ำมักลดขนาดปัญหาเป็นครึ่งหรือเป็นชิ้นใด ๆ ที่เล็กกว่า N8 Divide-and-conquer bounds ขอบเขตอัลกอริทึมแบ่งครึ่ง $$\begin{gathered} T(n) = T\big(\lfloor\tfrac n2\rfloor\big) + T\big(\lceil\tfrac n2\rceil\big) + n \\ \Rightarrow\ T(n) \le n\lceil\log_2 n\rceil \\ C(n) = 1 + C\big(\lfloor\tfrac n2\rfloor\big) \ \Rightarrow\ C(n) = \lfloor\log_2 n\rfloor + 1 \end{gathered}$$ $T(1) = 0,\ C(1) = 1$ · merge sort และ binary search ตามลำดับ N9 Take-away games เกมหยิบ (P/N positions) $$\begin{gathered} n \text{ แพ้} \iff \text{ทุกการหยิบนำไปสู่ตำแหน่งชนะ} \\ \text{หยิบ } \{1, \dots, k\}:\ n \text{ แพ้} \iff (k+1) \mid n \end{gathered}$$ ตำแหน่ง 0 เป็นกรณีฐาน (คนที่ต้องเดินแพ้) ทุกตำแหน่งตัดสินจากตำแหน่งที่เล็กกว่าหลายตัว ตัวอย่าง N-13 · เกมหยิบเหรียญ ### มีเหรียญ n อัน ผลัดกันหยิบครั้งละ 1, 2 หรือ 3 อัน ผู้หยิบอันสุดท้ายชนะ พิสูจน์ว่าผู้เริ่มก่อนแพ้ก็ต่อเมื่อ $4 \mid n$ - $P(n)$: ตำแหน่ง n แพ้ (สำหรับคนที่ต้องเดิน) ⇔ $4 \mid n$ · กรณีฐาน $n = 0$: ไม่มีให้หยิบ แพ้ และ $4 \mid 0$ ✓ - ให้ $n \ge 1$ และสมมติ $P(j)$ ทุก $j < n$ ถ้า $4 \mid n$: ทุกการหยิบได้ $n - 1, n - 2, n - 3$ ซึ่งหาร 4 ไม่ลงตัว จึงเป็นตำแหน่งชนะตาม ${P(n-1)}$, ${P(n-2)}$, ${P(n-3)}$ ⇒ n แพ้ - ถ้า $4 \nmid n$: หยิบ $n \bmod 4$ อันไปที่พหุคูณของ 4 ซึ่งแพ้ตามสมมติฐาน ⇒ n ชนะ ∎ กลยุทธ์: ทิ้งพหุคูณของ 4 ให้คู่แข่งเสมอ ลองชนะคอมพิวเตอร์ในแล็บ ตัวอย่าง N-14 · merge sort ### $T(1) = 0,\ T(n) = T(\lfloor n/2\rfloor) + T(\lceil n/2\rceil) + n$ พิสูจน์ $T(n) \le n\lceil\log_2 n\rceil$ - กรณีฐาน $T(1) = 0 \le 1\cdot 0$ · ให้ $n \ge 2$ และ $c = \lceil\log_2 n\rceil$ จึงมี $n \le 2^c$ - $\lceil n/2\rceil \le 2^{c-1}$ ⇒ ทั้งสองครึ่งมี $\lceil\log_2(\cdot)\rceil \le c - 1$ และเล็กกว่า n จึงใช้ ${\text{สมมติฐานแบบเข้ม}}$ ได้ - $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$ ตัวอย่าง N-15 · binary search ### $C(1) = 1,\ C(n) = 1 + C(\lfloor n/2\rfloor)$ พิสูจน์ $C(n) = \lfloor\log_2 n\rfloor + 1$ - กรณีฐาน $C(1) = 1 = 0 + 1$ · ให้ $n \ge 2$ สมมติสูตรจริงทุก $j < n$ โดยเฉพาะ $j = \lfloor n/2\rfloor$ - ถ้า $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$ - $C(n) = 1 + {(m - 1) + 1} = m + 1 = \lfloor\log_2 n\rfloor + 1$ ∎ ค้นข้อมูลล้านรายการ (เรียงแล้ว) ใช้ไม่เกิน 20 รอบ ตัวอย่าง N-16 · เอกลักษณ์ของเบซู ### พิสูจน์ว่า $\gcd(a, b) = ax + by$ สำหรับจำนวนเต็ม x, y บางค่า (ทุก $a \ge 0,\ b \ge 0$ ไม่เป็นศูนย์พร้อมกัน) แล้วหา x, y ของ $\gcd(252, 198)$ - อุปนัยแบบเข้มบน b · กรณีฐาน $b = 0$: $\gcd(a, 0) = a = a\cdot1 + 0\cdot0$ - ให้ $b \ge 1$: $a = qb + r$ โดย $0 \le r < b$ และ $\gcd(a, b) = \gcd(b, r)$ จาก ${P(r)}$ (เพราะ $r < b$): $\gcd(b, r) = bx' + ry'$ - แทน $r = a - qb$: $\gcd(a,b) = ay' + b(x' - qy')$ ∎ (นี่คืออัลกอริทึมยุคลิดแบบขยาย) - $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 จึงต้องใช้อุปนัยแบบเข้ม ตัวอย่าง N-17 · ระบบควบคุมดิจิทัล ### ค่าความคลาดของลูปควบคุมแบบไม่ต่อเนื่องสอดคล้อง $e_n = 0.5e_{n-1} + 0.3e_{n-2}$ โดย $e_0 = e_1 = 1$ พิสูจน์ว่า $e_n \le C(0.86)^n$ และหา C - สัมประสิทธิ์ไม่ติดลบ ใช้ 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 ไม่ได้) - กรณีฐานสองตัว: ต้องการ $C \ge e_0 = 1$ และ $C \ge e_1/0.86 = 1.1628$ ⇒ เลือก $C = 1.1628$ - ขั้นอุปนัยแบบเข้ม: $e_n \le 0.5\,{Cr^{n-1}} + 0.3\,{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$ ## เปรียบเทียบ: อุปนัยธรรมดา อุปนัยแบบเข้ม และหลักการจัดอันดับดี | | อุปนัยธรรมดา | อุปนัยแบบเข้ม | หลักการจัดอันดับดี | | สมมติ | $P(k)$ | $P(n_0), \dots, P(n-1)$ ทั้งหมด | มีตัวอย่างค้านที่เล็กที่สุด n | | พิสูจน์ | $P(k+1)$ | $P(n)$ | ได้ตัวอย่างค้านที่เล็กกว่า n (ขัดแย้ง) | | เหมาะกับ | สูตรผลบวก การหารลงตัว อสมการทีละขั้น | เวียนเกิดหลายขั้น ตัวประกอบ แบ่งครึ่ง แบ่งชิ้น | พิสูจน์การมีอยู่ ความเป็นอตรรกยะ การสิ้นสุดของอัลกอริทึม | | กรณีฐาน | ส่วนใหญ่ 1 ตัว | เท่ากับจำนวนขั้นที่ย้อนไกลที่สุด | มักแฝงอยู่ในการแยกกรณี | ทั้งสามแบบพิสูจน์สิ่งเดียวกันได้เสมอ (N2) การเลือกแบบเข้มไม่ได้ทำให้บทพิสูจน์ “แข็งแรงกว่า” แต่ทำให้เขียนง่ายและอ่านเข้าใจกว่าเมื่อขั้นอุปนัยต้องการหลายกรณี ถ้าใช้แค่ $P(k)$ ก็เขียนแบบธรรมดาได้ ไม่ผิด ## ข้อผิดพลาดที่พบบ่อย: เกมหาจุดผิด - กรณีฐานไม่พอ: ย้อนสองขั้นแต่ตรวจแค่ตัวเดียว (ผิดบ่อยที่สุด) - อ้างกรณีที่อยู่นอกโดเมน: ใช้ $P(n-3)$ เมื่อ $n - 3$ ยังต่ำกว่า $n_0$ หรือใช้ $a - 1 = 0$ ที่ไม่ใช่จำนวนนับ - อ้างสมมติฐานถูก แต่ตรรกะต่อจากนั้นผิด: เช่น “ผลคูณของจำนวนเฉพาะเป็นจำนวนเฉพาะ” - เขียนสมมติฐานไม่ครบ: ต้องบอกช่วง “ทุก $n_0 \le j < n$” ไม่ใช่ “สมมติว่าจริง” ## ฝึกพิสูจน์แบบภาคปฏิบัติ ### เรียงบรรทัดบทพิสูจน์ (มีบรรทัดหลอก) บทพิสูจน์ที่ได้คะแนนเต็มคือบทพิสูจน์ที่เรียงเหตุผลถูก แตะบรรทัดตามลำดับ ระวังบรรทัดหลอกที่ดูน่าเชื่อแต่ใช้ไม่ได้ เช่น “สมมติแค่ P(n − 1)” ในโจทย์ที่ต้องย้อนสามขั้น ### โจทย์ฝึก 10 ข้อ (มีเฉลย) S1 พื้นฐานพิสูจน์ว่าทุกราคา $n \ge 12$ บาทรวมได้ด้วยแสตมป์ 4 และ 5 บาท กรณีฐาน 4 ตัว: $12 = 4\cdot3,\ 13 = 4\cdot2 + 5,\ 14 = 4 + 5\cdot2,\ 15 = 5\cdot3$ ขั้นอุปนัย: $n \ge 16$ ⇒ $n - 4 \ge 12$ ใช้ $P(n-4)$ แล้วเติม 4 บาท $g(4,5) = 11$ S2 พื้นฐานมีเหรียญ 6, 9, 20 (ชุดไก่ทอด) ราคาใดใหญ่สุดที่ซื้อพอดีไม่ได้ ไล่ตารางพบว่า 44, 45, 46, 47, 48, 49 ทำได้ครบหกค่าติดกัน (เท่ากับเหรียญที่เล็กที่สุด) จึงทำได้ทุกค่าที่มากกว่าด้วยการเติม 6 ค่าที่ทำไม่ได้ใหญ่สุดคือ 43 43 S3 พื้นฐาน$a_1 = 1,\ a_2 = 3,\ a_n = a_{n-1} + a_{n-2}$ พิสูจน์ $a_n < (7/4)^n$ กรณีฐาน $1 < 1.75,\ 3 < 3.0625$ ขั้นอุปนัย: $a_n < (7/4)^{n-1} + (7/4)^{n-2} = (7/4)^{n-2}\cdot\tfrac{11}{4}$ และ $\tfrac{11}{4} < \tfrac{49}{16}$ ✓ ใช้ได้เพราะ $\tfrac{4}{7} + \tfrac{16}{49} = \tfrac{44}{49} \le 1$ S4 กลาง$a_0 = 1,\ a_1 = 4,\ a_n = 5a_{n-1} - 6a_{n-2}$ พิสูจน์ $a_n = 2\cdot3^n - 2^n$ กรณีฐาน $2 - 1 = 1,\ 6 - 2 = 4$ ขั้นอุปนัย: $5(2\cdot3^{n-1} - 2^{n-1}) - 6(2\cdot3^{n-2} - 2^{n-2}) = 2\cdot3^{n-2}(15 - 6) - 2^{n-2}(10 - 6) = 2\cdot3^n - 2^n$ ✓ S5 กลางพิสูจน์ว่า $F_1 + F_2 + \dots + F_n = F_{n+2} - 1$ อุปนัยธรรมดาพอ (ใช้แค่ P(n−1)): $\sum_{k=1}^{n} F_k = (F_{n+1} - 1) + F_n = F_{n+2} - 1$ · ตัวอย่างนี้แสดงว่าไม่ต้องใช้แบบเข้มทุกครั้ง กรณีฐาน $F_1 = 1 = F_3 - 1$ S6 กลางเกมหยิบครั้งละ 1, 3 หรือ 4 อัน ตำแหน่งใดแพ้ ไล่ตาราง: 0 แพ้, 1 ชนะ, 2 แพ้, 3, 4, 5, 6 ชนะ, 7 แพ้, … ตำแหน่งแพ้คือ $n \equiv 0, 2 \pmod 7$ พิสูจน์ด้วยอุปนัยแบบเข้มเพราะตำแหน่ง n ขึ้นกับ n−1, n−3, n−4 0, 2, 7, 9, 14, 16, … S7 กลางพิสูจน์ว่าต้นไม้ (tree) ที่มี n จุดยอดมีเส้นเชื่อม $n - 1$ เส้น อุปนัยแบบเข้มบน n: ลบเส้นเชื่อมหนึ่งเส้นได้ต้นไม้สองต้นขนาด $p + q = n$ จากสมมติฐานมีเส้น $(p-1) + (q-1)$ รวมเส้นที่ลบกลับคืน $= n - 1$ (โครงสร้างเดียวกับช็อกโกแลต) กรณีฐาน n = 1 มี 0 เส้น S8 ขั้นสูง$a_1 = 1,\ a_n = a_{\lfloor n/2\rfloor} + a_{\lceil n/2\rceil}$ สำหรับ $n \ge 2$ หาและพิสูจน์สูตร ลองค่า: 1, 2, 3, 4, … เดา $a_n = n$ ขั้นอุปนัย $a_n = \lfloor n/2\rfloor + \lceil n/2\rceil = n$ ใช้ $P(\lfloor n/2\rfloor), P(\lceil n/2\rceil)$ ซึ่งทั้งคู่ $< n$ เมื่อ $n \ge 2$ $a_n = n$ S9 ขั้นสูงพิสูจน์ว่า $\sqrt2$ เป็นจำนวนอตรรกยะด้วยหลักการจัดอันดับดี สมมติ $\sqrt2 = p/q$ และให้ q เป็นตัวส่วนบวกที่เล็กที่สุด ได้ $p^2 = 2q^2$ ⇒ p คู่ ⇒ q คู่ ⇒ $\sqrt2 = (p/2)/(q/2)$ มีตัวส่วนเล็กกว่า q ขัดแย้ง เป็นรูป “ตัวอย่างค้านที่เล็กที่สุด” ของอุปนัยแบบเข้ม S10 ขั้นสูง$e_n = 0.6e_{n-1} + 0.2e_{n-2},\ e_0 = 2,\ e_1 = 1$ หา r ที่เล็กที่สุดที่ $e_n \le Cr^n$ พิสูจน์ได้ด้วยวิธี N7 r ต้องสอดคล้อง $0.6/r + 0.2/r^2 \le 1$ ⇔ $r^2 - 0.6r - 0.2 \ge 0$ ⇒ $r \ge 0.3 + \sqrt{0.29} \approx 0.8385$ เลือก r ใดก็ได้ที่ไม่น้อยกว่านี้ แล้วให้ $C = \max(e_0, e_1/r)$ $r_{\min} = 0.3 + \sqrt{0.29} \approx 0.8385$ ## เรียนต่อ ทบทวนอุปนัยธรรมดาและแม่แบบ 4 ขั้นที่ อุปนัยเชิงคณิตศาสตร์ (3.2) อ่านตัวอย่างอีก 14 ข้อใน บทความอุปนัยเชิงคณิตศาสตร์ หาสูตรที่จะพิสูจน์ด้วย เครื่องคิดเลขลำดับและอนุกรม (26.11) และดูทฤษฎีลำดับเวียนเกิดที่ ลำดับ (26.1) ## คำถามที่พบบ่อย อุปนัยแบบเข้ม (strong induction) ต่างจากอุปนัยธรรมดาอย่างไร? อุปนัยธรรมดาสมมติเพียง $P(k)$ แล้วพิสูจน์ $P(k+1)$ ส่วนอุปนัยแบบเข้มสมมติว่า $P(j)$ จริงทุก j ตั้งแต่กรณีฐานจนถึง $n-1$ แล้วพิสูจน์ $P(n)$ ใช้เมื่อการพิสูจน์ $P(n)$ ต้องอาศัยกรณีที่ย้อนไปไกลกว่าหนึ่งขั้นหรือไม่รู้ล่วงหน้าว่าย้อนไปเท่าไร เช่น $P(n-2)$, $P(\lfloor n/2\rfloor)$ หรือตัวประกอบของ n ทั้งสองแบบมีพลังเท่ากันในทางตรรกะ ต้องมีกรณีฐานกี่ตัว? เท่ากับจำนวนขั้นที่ขั้นอุปนัยย้อนกลับไกลที่สุด ถ้าใช้ $P(n-1)$ และ $P(n-2)$ ต้องมีกรณีฐานสองตัว (เช่น $F_1$ และ $F_2$) ถ้าใช้ $P(n-4)$ แบบโจทย์แสตมป์ 4 และ 5 บาทต้องมีสี่ตัว ถ้าขาดไปแม้ตัวเดียว ทั้งบทพิสูจน์ใช้ไม่ได้ พิสูจน์ว่าทุกราคาตั้งแต่ 8 บาทขึ้นไปรวมได้ด้วยแสตมป์ 3 และ 5 บาทอย่างไร? กรณีฐาน $8 = 3+5,\ 9 = 3+3+3,\ 10 = 5+5$ ขั้นอุปนัยแบบเข้ม: ให้ $n \ge 11$ และสมมติว่าทุกราคา j ที่ $8 \le j ทำไมการพิสูจน์ว่าทุกจำนวนเต็มเป็นผลคูณของจำนวนเฉพาะต้องใช้อุปนัยแบบเข้ม? เพราะถ้า n ไม่เป็นจำนวนเฉพาะ n = ab โดย a และ b เล็กกว่า n แต่ไม่ใช่ n − 1 การรู้ว่า n − 1 เป็นผลคูณของจำนวนเฉพาะไม่ช่วยอะไรเลย ต้องสมมติว่าทุกจำนวนที่เล็กกว่า n เป็นผลคูณของจำนวนเฉพาะ จึงใช้สมมติฐานกับ a และ b ได้ อุปนัยแบบเข้มใช้ในงานวิศวกรรมหรือวิทยาการคอมพิวเตอร์อย่างไร? ใช้พิสูจน์ความถูกต้องและเวลาทำงานของอัลกอริทึมแบบแบ่งแล้วเอาชนะ (เช่น merge sort ใช้การเปรียบเทียบไม่เกิน $n\lceil\log_2 n\rceil$ ครั้ง binary search ใช้ $\lfloor\log_2 n\rfloor + 1$ รอบ) พิสูจน์สูตรปิดของลำดับเวียนเกิดในตัวกรองดิจิทัล และพิสูจน์ว่าค่าความคลาดในระบบควบคุมดิจิทัลลดลงแบบเรขาคณิต $|e_n| \le Cr^n$ มีที่ให้ฝึกเขียนพิสูจน์ด้วยอุปนัยแบบเข้มไหม? หน้านี้มีแล็บโต้ตอบ 11 ชุด เช่น ตารางว่าแต่ละ P(n) อาศัยกรณีใด ทดลองลดกรณีฐานแล้วดูบทพิสูจน์พัง เกมเรียงบรรทัดบทพิสูจน์ที่มีบรรทัดหลอก เกมหาจุดผิด และเครื่องแก้ความสัมพันธ์เวียนเกิดที่สร้างบทพิสูจน์ด้วยอุปนัยแบบเข้มให้อัตโนมัติ พร้อมโจทย์ฝึกที่มีเฉลย มด อาจารย์มด · ธีรวุฒิ แสวงบุญ อาจารย์สาขาวิชาวิศวกรรมไฟฟ้า มหาวิทยาลัยราชภัฏธนบุรี สมุทรปราการ · ดูโปรไฟล์ ## คำถามที่พบบ่อย (FAQ) **อุปนัยแบบเข้ม (strong induction) ต่างจากอุปนัยธรรมดาอย่างไร?** อุปนัยธรรมดาสมมติเพียง $P(k)$ แล้วพิสูจน์ $P(k+1)$ ส่วนอุปนัยแบบเข้มสมมติว่า $P(j)$ จริงทุก j ตั้งแต่กรณีฐานจนถึง $n-1$ แล้วพิสูจน์ $P(n)$ ใช้เมื่อการพิสูจน์ $P(n)$ ต้องอาศัยกรณีที่ย้อนไปไกลกว่าหนึ่งขั้นหรือไม่รู้ล่วงหน้าว่าย้อนไปเท่าไร เช่น $P(n-2)$, $P(\lfloor n/2\rfloor)$ หรือตัวประกอบของ n ทั้งสองแบบมีพลังเท่ากันในทางตรรกะ **ต้องมีกรณีฐานกี่ตัว?** เท่ากับจำนวนขั้นที่ขั้นอุปนัยย้อนกลับไกลที่สุด ถ้าใช้ $P(n-1)$ และ $P(n-2)$ ต้องมีกรณีฐานสองตัว (เช่น $F_1$ และ $F_2$) ถ้าใช้ $P(n-4)$ แบบโจทย์แสตมป์ 4 และ 5 บาทต้องมีสี่ตัว ถ้าขาดไปแม้ตัวเดียว ทั้งบทพิสูจน์ใช้ไม่ได้ **พิสูจน์ว่าทุกราคาตั้งแต่ 8 บาทขึ้นไปรวมได้ด้วยแสตมป์ 3 และ 5 บาทอย่างไร?** กรณีฐาน $8 = 3+5,\ 9 = 3+3+3,\ 10 = 5+5$ ขั้นอุปนัยแบบเข้ม: ให้ $n \ge 11$ และสมมติว่าทุกราคา j ที่ $8 \le j < n$ รวมได้ เพราะ $n - 3 \ge 8$ จึงรวม $n-3$ ได้ แล้วเติมแสตมป์ 3 บาทอีกดวง ต้องมีกรณีฐานสามตัวเพราะขั้นอุปนัยย้อนกลับ 3 ขั้น **ทำไมการพิสูจน์ว่าทุกจำนวนเต็มเป็นผลคูณของจำนวนเฉพาะต้องใช้อุปนัยแบบเข้ม?** เพราะถ้า n ไม่เป็นจำนวนเฉพาะ n = ab โดย a และ b เล็กกว่า n แต่ไม่ใช่ n − 1 การรู้ว่า n − 1 เป็นผลคูณของจำนวนเฉพาะไม่ช่วยอะไรเลย ต้องสมมติว่าทุกจำนวนที่เล็กกว่า n เป็นผลคูณของจำนวนเฉพาะ จึงใช้สมมติฐานกับ a และ b ได้ **อุปนัยแบบเข้มใช้ในงานวิศวกรรมหรือวิทยาการคอมพิวเตอร์อย่างไร?** ใช้พิสูจน์ความถูกต้องและเวลาทำงานของอัลกอริทึมแบบแบ่งแล้วเอาชนะ (เช่น merge sort ใช้การเปรียบเทียบไม่เกิน $n\lceil\log_2 n\rceil$ ครั้ง binary search ใช้ $\lfloor\log_2 n\rfloor + 1$ รอบ) พิสูจน์สูตรปิดของลำดับเวียนเกิดในตัวกรองดิจิทัล และพิสูจน์ว่าค่าความคลาดในระบบควบคุมดิจิทัลลดลงแบบเรขาคณิต $|e_n| \le Cr^n$ **มีที่ให้ฝึกเขียนพิสูจน์ด้วยอุปนัยแบบเข้มไหม?** หน้านี้มีแล็บโต้ตอบ 11 ชุด เช่น ตารางว่าแต่ละ P(n) อาศัยกรณีใด ทดลองลดกรณีฐานแล้วดูบทพิสูจน์พัง เกมเรียงบรรทัดบทพิสูจน์ที่มีบรรทัดหลอก เกมหาจุดผิด และเครื่องแก้ความสัมพันธ์เวียนเกิดที่สร้างบทพิสูจน์ด้วยอุปนัยแบบเข้มให้อัตโนมัติ พร้อมโจทย์ฝึกที่มีเฉลย