พิสูจน์โดยอุปนัยเชิงคณิตศาสตร์

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






อุปนัยเชิงคณิตศาสตร์ : ให้ S
1. 1  S
2. สำหรับจำนวนเต็มบวก k ถ้า k  S แล้ว k+1  S ด้วย
จะได้ว่า S =
เราเรียก ประโยคในข้อ 1. ว่า มูลฐานของการอุปนัย (basis of induction) และ 
ประโยคข้อ 2. ว่า ขั้นอุปนัย (inductive step) และเรียกสมมติฐานในประโยคข้อ 2. ที่ว่า k  S ว่า สมมติฐานของการอุปนัย (inductive hypothesis)
ตัวอย่าง จงพิสูจน์ว่า

1. 12 + 22 + 32 + . . . + n2 = n(2n+1)(n+1)/6
2. 1 + 3 + 5 + 7 + . . . + (2 n - 1) = n2
3. n < 2n
4. n3 - n หารด้วย 3 ลงตัว
5. 1 + 2 + 22 + . . . + 2n = 2n+1 - 1
6. 1 + 2 + 3 + . . . + n = n (n + 1)/2
7. 2n < n! สำหรับทุก n > 3

ยกตัวอย่าง

Ex1 จงพิสูจน์ว่า 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 ลงตัว 

อ้างอิง จาก 
http://th.tni.wikia.com/wiki/อุปนัยเชิงคณิตศาสตร์
http://pioneer.netserv.chula.ac.th/~skrung/2301365/Lecture002.html


        คณิตศาสตร์

  ในความพิศวง จะเจอหนทางที่สว่าง




- แนะนำเพื่อน สอนคอมพิวเตอร์
   ครูคอมฯ IACubru