อุปนัยเชิงคณิตศาสตร์

อุปนัยเชิงคณิตศาสตร์ (mathematical induction) เป็นวิธีการพิสูจน์ทางคณิตศาสตร์วิธีหนึ่ง

เนื้อหา

อุปนัยเชิงคณิตศาสตร์ (Mathematical Induction) คือการพิสูจน์สำหรับประโยคที่มีตัวแปรเป็นจำนวนนับ 

โดยการพิสูจน์อาศัยหลักที่ว่า ประโยคเริ่มต้นเป็นจริง (คือ P(1) เป็นจริง)
และถ้าเราสามารถแสดงว่า การพิสูจน์ค่าความจริงของประโยค P(n+1) เกิดจากค่าความจริงของประโยค P(n)
เราจะได้ว่า P(n) เป็นจริงทุกค่าของ n

Added by Annwinnie

หลักอุปนัยเชิงคณิตศาสตร์

สำหรับแต่ละจำนวนเต็มบวก n ให้ P(n) แทนข้อความที่เกี่ยวข้องกับ n
ถ้า     1)   P(1) เป็นจริง 

 และ   2)   สำหรับจำนวนเต็มบวก k ใดๆ ถ้า P(k) เป็นจริงแล้ว P(k+1)  เป็นจริงด้วย
จะสรุปได้ว่า P(n) เป็นจริง สำหรับทุกๆ จำนวนเต็มบวก n

เราลองเปรียบเทียบการอุปนัยเชิงคณิตศาสตร์ กับการล้มของโดมิโน
ถ้าเราเอาโดมิโนมาตั้งเรียงเป็นแถวยาว แล้วเรารู้ว่า
1. โดมิโนตัวแรกล้ม
2. ไม่ว่า k จะเป็นอะไรก็ตาม ถ้าโดมิโนตัวที่ k ล้มแล้วโดมิโนตัวที่ k+1 ล้มด้วย เราก็จะรู้ว่า ตัวที่ 1 ล้มทำให้ตัวที่ 2 ล้ม ตัวที่ 2 ล้มทำให้ตัวที่ 3 ล้ม ตัวที่ 3 ล้มทำให้ตัวที่ 4 ล้ม ไปเรื่อยๆจนหมดแถว เราก็จะสรุปได้ว่าโดมิโนล้มทุกตัว
ทีนี้ลองมาดูการอุปนัยเชิงคณิตศาสตร์บ้าง เราจะพิสูจน์ว่า P(n) (ประพจน์ในตัวแปร n) เป็นจริงสำหรับทุกจำนวนนับ n
1. เราก็ต้องบอกว่าตัวแรกจริงก่อน ก็คือบอกว่า P(1) เป็นจริง [เหมือนเอา 1 ไปแทนที่ n] 2. สำหรับทุกๆ k ถ้าตัวที่ k จริงแล้วตัวที่ k+1 จริงด้วย ก็คือบอกว่า P(k) เป็นจริงแล้ว P(k+1) จริงด้วย
ถ้าเราได้สองข้อนี้ก็จะสรุปได้ว่า P(n) จริงสำหรับทุกจำนวนนับ n

ตัวอย่าง จงพิสูจน์ว่า 1+3+5+7+…+(2n –1) = n² สำหรับทุก ๆ จำนวนเต็มบวก n

วิธีทำ ให้ P(n) แทนข้อความ 1+3+5+7+…+(2n – 1) = n² ……… (1)

1. จะพิสูจน์ P(1) เป็นจริง
                   เมื่อ n = 1 จะได้ว่า
                   ทางซ้ายมือของสมการ (1) คือ 1
         ทางขวามือของสมการ (1) คือ 12 = 1

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

2. จะพิสูจน์ว่า ถ้า P(k) เป็นจริง แล้ว P(k+1) เป็นจริงด้วย
                   สมมติว่า p(k) เป็นจริง
                   นั่นคือ 1+3+5+…+(2k –1) = k2 ……… (2)
         จะพิสูจน์ว่า P(k+1) เป็นจริงด้วย กล่าวคือ จะพิสูจน์ว่า
                   1+3+5+…+[2(k + 1) – 1] = (k + 1)2 ……… (3)
         พิจารณาทางซ้ายมือของสมการ (3) จะได้ว่า
                   1+3+5+…+[2(k + 1) – 1] = 1+3+5+…+(2k – 1) + [2(k + 1) – 1]
          = k2 + [2(k + 1) – 1]
          = k2 + 2k + 1
          = (k + 1)2

ดังนั้น P(k + 1) เป็นจริง
     เพราะฉะนั้น   โดยหลักการอุปนัยเชิงคณิตศาสตร์ จะได้ว่า P(n) เป็นจริง สำหรับทุก ๆ จำนวนเต็มบวก n

Ex2 จงพิสูจน์ว่า n³ – n หารด้วย 3 ลงตัว สำหรับทุก ๆ จำนวนเต็มบวก n
วิธีทำ ให้ P(n) แทนข้อความ n³ - n หารด้วย 3 ลงตัว
1. จะแสดงว่า P(1) เป็นจริง
เมื่อ n = 1 จะได้ 1³ – 1 = 0 ซึ่งหารด้วย 3 ลงตัว ดังนั้น P(1) เป็นจริง
2. จะแสดงว่า ถ้า P(k) เป็นจริง แล้ว p(k) เป็นจริงด้วย
สมมติว่า ถ้า P(k) เป็นจริง นั่นคือ k³ - k หารด้วย 3 ลงตัว
จะพิสูจน์ว่า P(k + 1) เป็นจริง กล่าวคือ
จะพิสูจน์ว่า (k + 1)³ – (k + 1) หารด้วย 3 ลงตัว
เนื่องจาก k³ - k หารด้วย 3 ลงตัว
ดังนั้น ให้ k³ – k = 3a เมื่อ a เป็นจำนวนเต็ม
เพราะว่า (k + 1)³ – (k + 1) = (k³ + 3k² + 3k +1) – (k + 1)
= k³ + 3k² + 2k
= k³ –k + 3k² + 3k
= (k³ – k) + 3(k² + k)
= 3a + 3(k² + k)
= 3(a + k² + k)

เนื่องจาก a + k² + k เป็นจำนวนเต็ม จะได้ว่า (k + 1)³ – (k + 1) หารด้วย 3 ลงตัว

ดังนั้น P(k + 1) เป็นจริง
     เพราะฉะนั้น   โดยหลักการอุปนัยเชิงคณิตศาสตร์ จะได้ว่า P(n) เป็นจริง สำหรับทุก ๆ จำนวนเต็มบวก n