อุปนัยเชิงคณิตศาสตร์ (Mathematical Induction): หลักการ วิธีพิสูจน์ และตัวอย่าง

1. นิยาม ให้ $P(n)$ แทน $1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}$

2. กรณีฐาน $n = 1$: ซ้าย $= 1$ ขวา $= \dfrac{1\cdot 2}{2} = 1$ เท่ากัน $P(1)$ จริง

3. สมมติฐาน สมมติว่า $P(k)$ จริงสำหรับ $k \ge 1$ บางค่า: $1 + 2 + \cdots + k = \dfrac{k(k+1)}{2}$

4. เป้าหมาย ต้องแสดงว่า $1 + 2 + \cdots + k + (k+1) = \dfrac{(k+1)(k+2)}{2}$

5. ขั้นอุปนัย $\underbrace{1 + 2 + \cdots + k}_{\text{ก้อนของ } P(k)} + (k+1) = \hlP{\dfrac{k(k+1)}{2}} + (k+1)$ (โดยสมมติฐานการอุปนัย)

6. $= \dfrac{k(k+1) + 2(k+1)}{2} = \dfrac{(k+1)(k+2)}{2}$ ตรงกับเป้าหมาย $P(k+1)$ จริง

7. สรุป โดยหลักอุปนัยเชิงคณิตศาสตร์ $P(n)$ จริงทุก $n \ge 1$ ∎

สังเกตเทคนิคหลัก: “ดึงพจน์สุดท้ายออก” แล้วส่วนที่เหลือคือด้านซ้ายของ P(k) พอดี สีน้ำเงิน = บรรทัดที่ใช้สมมติฐาน ต้องมีอย่างน้อยหนึ่งจุดเสมอ

1. กรณีฐาน $n = 1$: ซ้าย $= 1$ ขวา $= \dfrac{1\cdot2\cdot3}{6} = 1$ จริง

2. สมมติ $\sum_{i=1}^{k} i^2 = \dfrac{k(k+1)(2k+1)}{6}$ ต้องแสดง $\sum_{i=1}^{k+1} i^2 = \dfrac{(k+1)(k+2)(2k+3)}{6}$

3. $\sum_{i=1}^{k+1} i^2 = \hlP{\dfrac{k(k+1)(2k+1)}{6}} + (k+1)^2 = \dfrac{(k+1)\left[k(2k+1) + 6(k+1)\right]}{6}$ (ดึง $k + 1$ เป็นตัวร่วม อย่ากระจายทั้งหมด)

4. $= \dfrac{(k+1)(2k^2 + 7k + 6)}{6} = \dfrac{(k+1)(k+2)(2k+3)}{6}$ ✓ ตรงกับเป้าหมาย

จริงทุก $n \ge 1$ · เคล็ดลับ: เขียนเป้าหมายไว้ก่อน แล้วรู้ว่าต้องแยกตัวประกอบให้ได้ $(k+2)(2k+3)$

1. กรณีฐาน $n = 1$: ซ้าย $= 1$ ขวา $= \dfrac{r - 1}{r - 1} = 1$ จริง

2. สมมติจริงที่ $n = k$: $1 + r + \cdots + r^{k} = \hlP{\dfrac{r^k - 1}{r - 1}} + r^k = \dfrac{r^k - 1 + r^{k+1} - r^k}{r - 1} = \dfrac{r^{k+1} - 1}{r - 1}$ ✓

3. เมื่อ $r = 2$: $1 + 2 + 4 + \cdots + 2^{n-1} = 2^n - 1$ คือค่าสูงสุดของเลขฐานสอง n บิต เช่น ADC 12 บิตมีรหัส 0 ถึง $2^{12} - 1 = 4095$

จริงทุก $n \ge 1$ (เทียบกับที่มาด้วยการคูณ r แล้วลบในหน้าลำดับและอนุกรม)

1. (ก) กรณีฐาน: $4^1 - 1 = 3$ หารด้วย 3 ลงตัว · สมมติ $4^k - 1 = 3m$

2. $4^{k+1} - 1 = 4\cdot 4^k - 1 = 4(4^k - 1) + 3 = 4\hlP{(3m)} + 3 = 3(4m + 1)$ หารด้วย 3 ลงตัว ✓

3. (ข) กรณีฐาน: $1^3 - 1 = 0 = 6\cdot 0$ ✓ · สมมติ $k^3 - k = 6m$

4. $(k+1)^3 - (k+1) = k^3 + 3k^2 + 3k + 1 - k - 1 = \hlP{(k^3 - k)} + 3k(k+1)$

5. $k(k+1)$ เป็นผลคูณของจำนวนเต็มสองตัวติดกัน จึงเป็นจำนวนคู่ $= 2t$ ดังนั้น $3k(k+1) = 6t$ และ $(k+1)^3 - (k+1) = 6m + 6t = 6(m + t)$ ✓

ทั้งสองจริงทุก $n \ge 1$ · (ข) ใช้ข้อเท็จจริงเสริมว่าจำนวนเต็มติดกันสองตัวมีตัวหนึ่งเป็นคู่ บทพิสูจน์อุปนัยหลายข้อต้องใช้ความรู้อื่นประกอบแบบนี้

1. ทำไมเริ่มที่ 5: $n = 2, 3, 4$ ได้ $4 = 4,\ 8 < 9,\ 16 = 16$ ไม่จริง ($n = 1$ จริงแต่ห่วงโซ่ขาดตอน)

2. กรณีฐาน $n = 5$: $2^5 = 32 > 25 = 5^2$ จริง

3. สมมติ $2^k > k^2$ สำหรับ $k \ge 5$ จะแสดง $2^{k+1} > (k+1)^2$

4. $2^{k+1} = 2\cdot 2^k > 2\hlP{k^2}$ (สมมติฐาน)

5. เหลือแสดง $2k^2 \ge (k+1)^2 \iff k^2 - 2k - 1 \ge 0 \iff (k-1)^2 \ge 2$ จริงเมื่อ $k \ge 3$ (โดยเฉพาะ $k \ge 5$) จึงได้ $2^{k+1} > 2k^2 \ge (k+1)^2$ ✓

จริงทุก $n \ge 5$ · ขั้นอุปนัยใช้ได้ตั้งแต่ k = 3 แต่ P(3) และ P(4) เป็นเท็จ กรณีฐานจึงต้องเป็นตัวแรกที่จริงแล้วโซ่ไม่ขาด คือ 5

1. กรณีฐาน $n = 1$: $1 + x \ge 1 + x$ จริง (เท่ากัน)

2. สมมติ $(1 + x)^k \ge 1 + kx$ เนื่องจาก $1 + x \ge 0$ คูณทั้งสองข้างแล้วเครื่องหมายไม่กลับ: $(1 + x)^{k+1} \ge \hlP{(1 + kx)}(1 + x)$

3. $= 1 + (k+1)x + kx^2 \ge 1 + (k+1)x$ เพราะ $kx^2 \ge 0$ ✓

4. ที่ $x = 0.05,\ n = 10$: $1.05^{10} \ge 1 + 10(0.05) = 1.5$ (ค่าจริง $1.629$) จุดที่ต้องระวังคือเงื่อนไข $x \ge -1$ ใช้ตอนคูณอสมการ

$(1 + x)^n \ge 1 + nx$ · ด้านขวาคือเทย์เลอร์อันดับหนึ่งของด้านซ้าย อสมการบอกว่าการประมาณเชิงเส้นไม่เคยเกินค่าจริงเมื่อ $x \ge -1$

1. (ก) กรณีฐานสี่ค่า: $12 = 4 + 4 + 4,\ 13 = 4 + 4 + 5,\ 14 = 4 + 5 + 5,\ 15 = 5 + 5 + 5$

2. ขั้นอุปนัย: ให้ $k \ge 15$ และสมมติว่าทุกราคา 12 ถึง k รวมได้ ราคา $k + 1 = (k - 3) + 4$ และ $12 \le k - 3 \le k$ จึงรวมได้ตามสมมติฐาน เติมแสตมป์ 4 บาทอีกดวง ✓ (ต้องย้อน 4 ขั้น จึงต้องมีกรณีฐาน 4 ค่า)

3. (ข) กรณีฐานสองค่า: $F_1 = 1 < 2$ และ $F_2 = 1 < 4$

4. สมมติ $F_j < 2^j$ ทุก $j \le k$ ($k \ge 2$): $F_{k+1} = \hlP{F_k} + \hlP{F_{k-1}} < 2^k + 2^{k-1} < 2^k + 2^k = 2^{k+1}$ ✓

(ก) ทุกราคา ≥ 12 บาท (11 บาทรวมไม่ได้) (ข) $F_n < 2^n$ ทุก n

1. กรณีฐาน: $0 < a_1 = \sqrt2 \approx 1.414 < 2$

2. สมมติ $0 < a_k < 2$: $a_{k+1} = \sqrt{2 + \hlP{a_k}} < \sqrt{2 + 2} = 2$ และ $a_{k+1} > \sqrt2 > 0$ ✓ จึงได้ $0 < a_n < 2$ ทุก n

3. เพิ่มขึ้น: $a_{n+1} > a_n \iff 2 + a_n > a_n^2 \iff (a_n - 2)(a_n + 1) < 0$ ซึ่งจริงเพราะ $0 < a_n < 2$ จากข้อก่อน (ไม่ต้องอุปนัยซ้ำ)

เพิ่มขึ้นและมีขอบเขต จึงลู่เข้า และลิมิตคือ 2 (ดูทฤษฎีบทลำดับทางเดียว S13)

1. กรณีฐาน $n = 1$: $\dfrac{d}{dx}x = 1 = 1\cdot x^0$ จริง (ได้จากนิยามอนุพันธ์โดยตรง)

2. สมมติ $\dfrac{d}{dx}x^k = kx^{k-1}$ แล้ว $\dfrac{d}{dx}x^{k+1} = \dfrac{d}{dx}\left(x\cdot x^k\right) = 1\cdot x^k + x\cdot\hlP{kx^{k-1}}$ (กฎผลคูณ + สมมติฐาน)

3. $= x^k + kx^k = (k+1)x^k$ ✓

จริงทุก n ∈ ℕ · กฎนี้คือฐานของสูตรอนุพันธ์ทั้งหมดของพหุนาม และของการหาอนุพันธ์อนุกรมกำลังทีละพจน์

1. กรณีฐาน $n = 1$: $\dfrac{d}{dx}x^{-1} = -x^{-2} = \dfrac{(-1)^1 1!}{x^2}$ จริง

2. สมมติจริงที่ k: $\dfrac{d^{k+1}}{dx^{k+1}}\dfrac1x = \dfrac{d}{dx}\hlP{\left[(-1)^k k!\,x^{-(k+1)}\right]} = (-1)^k k!\cdot(-(k+1))x^{-(k+2)} = \dfrac{(-1)^{k+1}(k+1)!}{x^{k+2}}$ ✓

3. สัมประสิทธิ์เทย์เลอร์ที่ $a = 1$: $c_n = \dfrac{f^{(n)}(1)}{n!} = (-1)^n$ จึงได้ $\dfrac1x = 1 - (x - 1) + (x - 1)^2 - \cdots$ (อนุกรมเรขาคณิตที่ $r = -(x - 1)$, $R = 1$)

$f^{(n)}(x) = (-1)^n n!\,x^{-(n+1)}$ · อุปนัยทำให้เราได้ “สูตรของอนุพันธ์ทุกอันดับ” ซึ่งเป็นสิ่งที่อนุกรมเทย์เลอร์ต้องการ

1. กรณีฐาน $n = 0$: $\mathcal{L}\{1\} = \int_0^{\infty} e^{-st}dt = \dfrac1s = \dfrac{0!}{s^1}$ จริง

2. สมมติ $\mathcal{L}\{t^k\} = \dfrac{k!}{s^{k+1}}$ อินทิเกรตทีละส่วนด้วย $u = t^{k+1},\ dv = e^{-st}dt$:

3. $\mathcal{L}\{t^{k+1}\} = \Big[-\dfrac{t^{k+1}e^{-st}}{s}\Big]_0^{\infty} + \dfrac{k+1}{s}\int_0^{\infty}t^k e^{-st}dt = 0 + \dfrac{k+1}{s}\cdot\hlP{\dfrac{k!}{s^{k+1}}}$ (พจน์ขอบเป็นศูนย์เพราะ $e^{-st}$ ชนะพหุนาม)

4. $= \dfrac{(k+1)!}{s^{k+2}}$ ✓

จริงทุก $n \ge 0$ ดูตารางการแปลงลาปลาซ · ที่ $s = 1$ ได้ $\int_0^\infty t^n e^{-t}dt = n!$ (ฟังก์ชันแกมมา)

1. กรณีฐาน: $\dfrac{F_3}{F_2} = \dfrac21 = 2 = R_1$ จริง

2. สมมติ $R_k = \dfrac{F_{2k+1}}{F_{2k}}$ แทนลงในความสัมพันธ์แล้วคูณเศษและส่วนด้วย $F_{2k}$: $R_{k+1} = \dfrac{1 + 2R_k}{1 + R_k} = \dfrac{F_{2k} + 2\hlP{F_{2k+1}}}{F_{2k} + \hlP{F_{2k+1}}}$

3. ใช้ $F_{m+1} = F_m + F_{m-1}$: ส่วน $= F_{2k+2}$ และเศษ $= F_{2k+2} + F_{2k+1} = F_{2k+3}$ จึงได้ $R_{k+1} = \dfrac{F_{2k+3}}{F_{2k+2}}$ ✓

$R_n = F_{2n+1}/F_{2n}$ ทุก n · อัตราส่วนเลขฟีโบนัชชีลู่เข้าสู่ $\varphi = \tfrac{1 + \sqrt5}{2}$ จึงได้ $R_\infty = \varphi R$ ตรงกับตัวอย่าง S-12

1. (ก) กรณีฐาน $n = 1$ ชัดเจน · สมมติจริงที่ k: $(\cos\theta + j\sin\theta)^{k+1} = \hlP{(\cos k\theta + j\sin k\theta)}(\cos\theta + j\sin\theta)$

2. $= (\cos k\theta\cos\theta - \sin k\theta\sin\theta) + j(\sin k\theta\cos\theta + \cos k\theta\sin\theta) = \cos(k+1)\theta + j\sin(k+1)\theta$ ✓

3. (ข) เดาจาก $A^2 = \begin{bmatrix}1 & 2T\\0 & 1\end{bmatrix}$: ข้อความ $A^n = \begin{bmatrix}1 & nT\\0 & 1\end{bmatrix}$ กรณีฐาน n = 1 จริง

4. $A^{k+1} = \hlP{A^k}A = \begin{bmatrix}1 & kT\\0 & 1\end{bmatrix}\begin{bmatrix}1 & T\\0 & 1\end{bmatrix} = \begin{bmatrix}1 & (k+1)T\\0 & 1\end{bmatrix}$ ✓ ดังนั้น $p_n = p_0 + nT\,v_0,\ v_n = v_0$

(ก) $(\cos\theta + j\sin\theta)^n = \cos n\theta + j\sin n\theta$ (ข) $p_n = p_0 + nTv_0$: เดาสูตรจากกรณีเล็ก แล้วยืนยันด้วยอุปนัย เป็นวิธีทำงานจริงของวิศวกร (ดูเมทริกซ์ยกกำลัง)

1. ข้อความคงที่ของลูป: “หลังจบรอบที่ k ค่า $s = k(k+1)/2$” · ก่อนเข้าลูป (k = 0): $s = 0 = 0\cdot1/2$ จริง

2. สมมติจริงหลังรอบที่ k รอบถัดไปทำ $s := s + (k+1)$ จึงได้ $\hlP{\tfrac{k(k+1)}{2}} + (k+1) = \tfrac{(k+1)(k+2)}{2}$ จริงหลังรอบที่ k + 1 · ลูปจบที่ k = n จึงได้ $s = n(n+1)/2$

3. สายเชื่อม: เครือข่าย k สถานีที่ต่อถึงกันทุกคู่มี $L_k$ เส้น เพิ่มสถานีใหม่ต้องลากสายไปหาทุกสถานีเดิมอีก k เส้น: $L_{k+1} = L_k + k$ และ $L_1 = 0$ อุปนัยให้ $L_n = \tfrac{n(n-1)}{2}$ เช่น 10 สถานีต้องใช้ 45 เส้น เหตุผลที่ระบบใหญ่เปลี่ยนไปใช้บัสหรือฟิลด์บัส

$s = n(n+1)/2$ · $L_n = n(n-1)/2$ · การพิสูจน์ loop invariant คืออุปนัยเชิงคณิตศาสตร์ที่ใช้ตรวจโค้ดPLCและเฟิร์มแวร์ที่ต้องปลอดภัย