อุปนัยทางคณิตศาสตร์ — หลักการ ขั้นตอน และตัวอย่าง

อุปนัยทางคณิตศาสตร์เป็นวิธีการพิสูจน์ที่ใช้แสดงว่าข้อความหนึ่งเป็นจริงสำหรับจำนวนเต็มทุกตัวตั้งแต่ค่าตั้งต้นค่าหนึ่งเป็นต้นไป หากต้องการพิสูจน์ข้อความสำหรับทุก $n \ge n_0$ คุณต้องแสดงว่ากรณีแรกเป็นจริง และแสดงต่อว่าถ้าจริงที่จำนวนเต็มตัวหนึ่งแล้ว จะบังคับให้จริงที่จำนวนเต็มตัวถัดไปด้วย

ถ้าทั้งสองส่วนถูกต้อง ข้อความนั้นก็จะเป็นจริงสำหรับจำนวนเต็มทุกตัวในช่วงที่ระบุ นี่คือแนวคิดทั้งหมดของวิธีนี้

อุปนัยทางคณิตศาสตร์ทำงานอย่างไร

เขียนข้อความที่ต้องการพิสูจน์ในรูป $P(n)$ แล้วโครงสร้างของการพิสูจน์แบบอุปนัยจะเป็นดังนี้:

1. พิสูจน์ กรณีฐาน: แสดงว่า $P(n_0)$ เป็นจริง
2. พิสูจน์ ขั้นอุปนัย: แสดงว่าถ้า $P(k)$ เป็นจริงสำหรับจำนวนเต็มใด ๆ $k \ge n_0$ แล้ว $P(k+1)$ ก็เป็นจริงด้วย

เมื่อทำครบสองส่วนนี้แล้ว คุณจึงสรุปได้ว่า $P(n)$ เป็นจริงสำหรับจำนวนเต็มทุกตัว $n \ge n_0$

ตรรกะของวิธีนี้เป็นแบบต่อเนื่อง กรณีฐานเป็นจุดเริ่มของโซ่ และขั้นอุปนัยทำให้โซ่นั้นเดินหน้าต่อไปทีละจำนวนเต็ม

ทำไมกรณีฐานและขั้นอุปนัยจึงสำคัญทั้งคู่

กรณีฐานให้ข้อความจริงตัวแรก ส่วนขั้นอุปนัยบอกว่าความจริงส่งต่อจากจำนวนเต็มตัวหนึ่งไปยังตัวถัดไปได้

ดังนั้นถ้า $P(n_0)$ เป็นจริง ก็จะได้ว่า $P(n_0 + 1)$ เป็นจริง จากนั้น $P(n_0 + 2)$ ก็เป็นจริงต่อไปเรื่อย ๆ การพิสูจน์แบบอุปนัยจะไม่ข้ามจุดเริ่มต้น และไม่ข้ามการเชื่อมจากกรณีหนึ่งไปยังกรณีถัดไป

ตัวอย่างทำจริง: พิสูจน์สูตรผลบวกด้วยอุปนัย

ตัวอย่างมาตรฐานคือสูตร

$$1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$$

สำหรับจำนวนเต็มทุกตัว $n \ge 1$

ให้

$$P(n): 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$$

กรณีฐาน

ให้ $n = 1$ ด้านซ้ายมีค่าเป็น $1$ และด้านขวาคือ

$$\frac{1(1+1)}{2} = 1$$

ดังนั้น $P(1)$ เป็นจริง

ขั้นอุปนัย

สมมติว่า $P(k)$ เป็นจริงสำหรับจำนวนเต็มใด ๆ ตัวหนึ่ง $k \ge 1$ นั่นคือ

$$1 + 2 + 3 + \cdots + k = \frac{k(k+1)}{2}$$

ตอนนี้พิสูจน์ $P(k+1)$ เริ่มจากด้านซ้ายของกรณี $k+1$:

$$1 + 2 + 3 + \cdots + k + (k+1)$$

ใช้สมมติฐานอุปนัย จะได้ว่า

$$\frac{k(k+1)}{2} + (k+1)$$

ดึง $(k+1)$ ออกเป็นตัวประกอบ:

$$(k+1)\left(\frac{k}{2} + 1\right)$$

จากนั้นจัดรูปอย่างง่าย:

$$(k+1)\left(\frac{k+2}{2}\right) = \frac{(k+1)(k+2)}{2}$$

ซึ่งตรงกับสูตรเดิมเมื่อ $n = k+1$ พอดี ดังนั้น $P(k+1)$ เป็นจริง

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

ควรใช้อุปนัยทางคณิตศาสตร์เมื่อไร

อุปนัยมีประโยชน์เมื่อข้อความขึ้นอยู่กับพารามิเตอร์ที่เป็นจำนวนเต็ม และแต่ละกรณีเชื่อมโยงกับกรณีก่อนหน้าได้อย่างเป็นธรรมชาติ เรื่องนี้พบได้บ่อยในผลบวก ข้อความเกี่ยวกับการหารลงตัว อสมการ ความสัมพันธ์เวียนเกิด และการพิสูจน์อัลกอริทึม

อันดับแรก ให้ระบุค่าตั้งต้นที่ถูกต้องก่อน บางข้อความเริ่มที่ $n = 0$ บางข้อความเริ่มที่ $n = 1$ และบางข้อความจะมีความหมายก็ต่อเมื่อ $n$ มีค่ามากกว่านั้น

จากนั้นตรวจสอบว่ากรณีถัดไปที่ถูกต้องคืออะไร โดยทั่วไปจะเป็นการก้าวจาก $k$ ไป $k+1$ แต่ถ้าข้อความกล่าวถึงเฉพาะจำนวนเต็มคู่ การก้าวจาก $k$ ไป $k+2$ อาจเป็นรูปแบบที่เหมาะสมกว่า

ข้อผิดพลาดที่พบบ่อยในการพิสูจน์แบบอุปนัย

พิสูจน์แค่กรณีฐาน

กรณีฐานตรวจสอบเพียงค่าตัวแรกเท่านั้น ถ้ามีแค่นี้อย่างเดียว ยังพิสูจน์ไม่ได้ว่าข้อความเป็นจริงสำหรับจำนวนเต็มตัวถัด ๆ ไป

ใช้ค่าตั้งต้นผิด

ถ้าข้อความต้องการสำหรับทุก $n \ge 2$ การพิสูจน์เพียง $P(1)$ ก็ไม่ช่วยอะไร กรณีฐานต้องตรงกับช่วงจริงของข้อความที่ต้องการพิสูจน์

ใช้สมมติฐานอุปนัยอย่างไม่ระมัดระวัง

ในขั้นอุปนัย คุณสมมติ $P(k)$ สำหรับจำนวนเต็มใด ๆ ตัวหนึ่ง $k$ ที่อยู่ในช่วงที่ถูกต้อง คุณไม่ได้สมมติว่าทฤษฎีบททั้งหมดถูกพิสูจน์แล้ว

พิสูจน์กรณีถัดไปผิดตัว

ถ้าทฤษฎีบทของคุณต้องการขั้น $k \to k+1$ การพิสูจน์ขั้นแบบอื่นจะยังไม่ทำให้การพิสูจน์สมบูรณ์ เว้นแต่คุณจะอธิบายว่าทำไมขั้นแบบนั้นจึงเพียงพอ

ส่วนขยายที่มีประโยชน์: อุปนัยเชิงแก่

บางครั้งการพิสูจน์ $P(k+1)$ ต้องใช้มากกว่าแค่ $P(k)$ ในสถานการณ์แบบนั้น อุปนัยเชิงแก่ จะให้คุณสมมติได้ว่าทุกกรณีก่อนหน้าจนถึง $k$ เป็นจริง แล้วจึงพิสูจน์กรณีถัดไป

แนวคิดนี้เกี่ยวข้องอย่างใกล้ชิดกับอุปนัยแบบปกติ แต่สมมติฐานจะแข็งแรงกว่า ตัวอย่างเช่น มันมีประโยชน์เมื่อการพิสูจน์ต้องอาศัยการแยกจำนวนหนึ่งออกเป็นส่วนที่เล็กกว่า

ลองพิสูจน์ด้วยตัวเอง

พิจารณาข้อความ

$$1 + 3 + 5 + \cdots + (2n - 1) = n^2$$

แล้วพิสูจน์ว่าสำหรับจำนวนเต็มทุกตัว $n \ge 1$ โดยใช้โครงสร้างเดียวกัน: เริ่มจากกรณีฐาน แล้วตามด้วยขั้นจาก $k$ ไป $k+1$ ถ้าคุณเขียนการพิสูจน์นี้ได้อย่างชัดเจน วิธีนี้ก็มักจะเริ่มเข้าใจได้จริง