✖

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

อุปนัยเชิงคณิตศาสตร์ (mathematical induction) เป็นวิธีพิสูจน์ที่ใช้บ่อยในคณิตศาสตร์ ส่วนใหญ่ใช้เมื่อทำงานกับจำนวนนับหรือกับลำดับอื่น ๆ

หลักการ

หลักการพื้นฐานคือ พิสูจน์ข้อความสำหรับสมาชิกตัวแรก ซึ่งในจำนวนนับส่วนใหญ่คือ n = 1 พิสูจน์ได้ด้วยการแทนค่าธรรมดา ในขั้นต่อไป คือขั้นอุปนัย พิสูจน์ประพจน์ “ถ้าข้อความเป็นจริงสำหรับ n = a แล้วข้อความเป็นจริงสำหรับ n = a + 1 ด้วย”

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

ตัวอย่างที่ 1

ตัวอย่างแรกเป็นตัวอย่างที่ชัดเจน จะพิสูจน์ว่า ถ้านำจำนวนคู่ใด ๆ บวกด้วยสอง จะได้จำนวนคู่อีก เนื่องจากเราพิจารณาจำนวนนับ จึงเขียนจำนวนคู่ทั่วไปเป็น 2n เมื่อ n เป็นจำนวนนับ ถ้าแทน n ด้วยจำนวนนับใด ๆ จะได้จำนวนคู่ ซึ่งเห็นได้ทันที การหารลงตัวเขียนด้วยเส้นตั้งดังนี้:

2∣2n

สัญลักษณ์นี้หมายความว่าสองหารนิพจน์ 2n ลงตัว เมื่อเขียนการหารลงตัวได้แล้ว ก็เขียนสิ่งที่ต้องพิสูจน์ด้วยอุปนัยเชิงคณิตศาสตร์ได้

2∣2n+2;n∈N

ในตัวอย่างแรกต้องพิสูจน์ข้อนี้ คือสองหารนิพจน์ 2n + 2 ลงตัว ซึ่งตรงกับโจทย์เดิมที่เป็นคำพูด “ถ้านำจำนวนคู่ใด ๆ บวกด้วยสอง จะได้จำนวนคู่อีก”

ขั้นฐานของอุปนัยพิสูจน์สำหรับสมาชิกตัวแรก คือหนึ่ง แทน n = 1 ในนิพจน์:

2∣2×1+22∣4

สองหารสี่ลงตัว ข้อความจึงเป็นจริงสำหรับสมาชิกตัวแรก ต่อไปเป็นขั้นอุปนัย ซึ่งต้องพิสูจน์ว่าถ้าเป็นจริงสำหรับสมาชิกตัวที่ a แล้วเป็นจริงสำหรับสมาชิกตัวที่ (a + 1) ด้วย เริ่มจากสมมติว่าสมมติฐานการอุปนัยเป็นจริง คือเมื่อ n = a:

2∣2a+2

สมมติว่านิพจน์นี้เป็นจริง และจะใช้ในการพิสูจน์ ตอนนี้ต้องการพิสูจน์ว่า

2∣2(a+1)+2

สิ่งที่ทำคือเขียน (a + 1) แทน a วงเล็บสำคัญมาก นิพจน์ต่อไปนี้ผิด: 2a + 1 + 2 เราไม่ได้บวกหนึ่งเข้ากับนิพจน์ทั้งหมด แต่ทำให้ a มากขึ้นหนึ่งจริง ๆ คือ (a + 1) จัดรูปนิพจน์ด้วยการคูณกระจายวงเล็บ

2∣2(a+1)+22∣2a+2+2 

ตอนนี้ขอแวะเรื่องการหารลงตัวเล็กน้อย ถ้ามีจำนวนสองจำนวน เช่น p และ q ซึ่งหารด้วยจำนวนหนึ่ง เช่น r ลงตัว แล้วผลบวกของทั้งสองจำนวนก็หารด้วย r ลงตัวด้วย จะได้ว่า:

(r∣p∧r∣q)⇒r∣(p+q)

ลองแทน เช่น p = 8 q = 20 และ r = 4 จะเห็นว่าสี่หารทั้งแปดและยี่สิบลงตัว และหารผลบวก 8 + 20 = 28 ลงตัวด้วย

จะใช้ข้อนี้ในตัวอย่างของเราอย่างไร แยกข้างขวาเป็นจำนวน p และ q ดังนี้:

p=2a+2;q=2

จำนวน q คือสอง หารด้วยสองลงตัวอย่างเห็นได้ชัด และนิพจน์ p ก็หารด้วยสองลงตัว เพราะสมมติฐานการอุปนัยบอกไว้ นิพจน์ p ตรงกับสมมติฐานการอุปนัยทุกประการ ซึ่งเราสมมติว่าเป็นจริง ถ้า p หารด้วยสองลงตัวและ q หารด้วยสองลงตัว แล้วผลบวกของทั้งสองก็หารด้วยสองลงตัว

กลับมาที่สมมติฐานการอุปนัยอีกครั้ง ตอนต้นเราบอกว่าสมมติว่า

2∣2a+2

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

อุปนัยจบเพียงเท่านี้ การพิสูจน์สำเร็จ ทฤษฎีบทเป็นจริง

ถ้าต้องการ ก็แยกอีกแบบหนึ่งได้โดยไม่ต้องใช้สมมติฐานการอุปนัย ให้ p = 2n และ q = 2 + 2 จำนวน q = 4 หารด้วยสองลงตัวอย่างเห็นได้ชัด p = 2n ก็เช่นกัน เพราะเมื่อหารด้วยสองจะเหลือ n ซึ่งเป็นจำนวนนับ คือเป็นจำนวนเต็ม จึงได้นิพจน์สองนิพจน์ที่หารด้วยสองลงตัวทั้งคู่อีกครั้ง ผลบวกของทั้งสองจึงหารด้วยสองลงตัวด้วย

แต่ไม่ว่าแบบใดเราก็พิสูจน์ได้ว่า

  1. นิพจน์เป็นจริงสำหรับ n = 1
  2. ถ้านิพจน์เป็นจริงสำหรับ n แล้วเป็นจริงสำหรับ n + 1 ด้วย

จากนี้จึงสรุปได้ว่า:

  • เรารู้ว่านิพจน์เป็นจริงสำหรับ n = 1
  • ถ้าเป็นจริงสำหรับ n ต้องเป็นจริงสำหรับ n + 1 ด้วย คือสำหรับ 1 + 1 นั่นคือนิพจน์เป็นจริงสำหรับ n = 2 ด้วย
  • ถ้าเป็นจริงสำหรับ n ต้องเป็นจริงสำหรับ n + 1 ด้วย คือสำหรับ 2 + 1 นั่นคือนิพจน์เป็นจริงสำหรับ n = 3 ด้วย
  • ถ้าเป็นจริงสำหรับ n ต้องเป็นจริงสำหรับ n + 1 ด้วย คือสำหรับ 3 + 1 นั่นคือนิพจน์เป็นจริงสำหรับ n = 4 ด้วย
  • ถ้าเป็นจริงสำหรับ n ต้องเป็นจริงสำหรับ n + 1 ด้วย คือสำหรับ 4 + 1 นั่นคือนิพจน์เป็นจริงสำหรับ n = 5 ด้วย
  • …

ตัวอย่างที่ 2

ต่อไปจะใช้อุปนัยเชิงคณิตศาสตร์พิสูจน์ข้อความง่าย ๆ:

2n≥2n;n∈N

เริ่มจากขั้นฐาน ตรวจว่าข้อความเป็นจริงสำหรับ n = 1 ซึ่งเป็นสมาชิกตัวแรกของจำนวนนับที่ n เลือกมาหรือไม่

21≥2×12≥2

ข้อนี้เป็นจริงอย่างเห็นได้ชัด ต่อไปเป็นขั้นอุปนัย ซึ่งต้องตรวจว่าถ้าเป็นจริงสำหรับ n = a แล้วเป็นจริงสำหรับ n = a + 1 ด้วยหรือไม่ สมมติฐานการอุปนัยคือ

2a≥2a

และต้องการพิสูจน์ว่า:

2a+1≥2(a+1)

ข้างซ้ายเขียนกระจายด้วยกฎของเลขยกกำลัง ส่วนข้างขวาคูณกระจาย

2⋅2a≥2a+2

ข้างซ้ายเปลี่ยนการคูณเป็นการบวก ข้างขวาคงไว้

2a+2a≥2a+2

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

2a≥2a2a≥2

บรรทัดแรกได้จากสมมติฐานการอุปนัย ส่วนข้อความที่สองเห็นได้ชัด (ค่าน้อยที่สุดของ 2a เกิดเมื่อ a = 1 ซึ่งเท่ากับสอง) จึงรู้ว่าพจน์แต่ละพจน์ทางข้างซ้ายมากกว่าหรือเท่ากับพจน์ที่คู่กันทางข้างขวา เป็นอันพิสูจน์ด้วยอุปนัยได้ว่าถ้านิพจน์เป็นจริงสำหรับ a แล้วเป็นจริงสำหรับ (a + 1) ด้วย และเนื่องจากนิพจน์เป็นจริงสำหรับหนึ่งด้วย นิพจน์นี้จึงเป็นจริง

ตัวอย่างที่ 3

ลองพิสูจน์ข้อความต่อไปนี้:

3∣n⇒3∣n2;n∈N

เป็นคำพูดคือ ถ้า n หารด้วยสามลงตัว แล้ว n2 หารด้วยสามลงตัวด้วย ถ้า n หารด้วยสามไม่ลงตัว นิพจน์เป็นจริงอย่างเห็นได้ชัด (ตามบทนิยามของประพจน์ที่มีตัวเชื่อม ถ้า…แล้ว) จึงพิจารณาเฉพาะกรณีที่ n หารด้วยสามลงตัว ซึ่งได้ลำดับของจำนวนนับ ai=3, 6, 9, 12, 15… ตั้งแต่นี้ไปจะพิจารณาเฉพาะในลำดับ ai นี้

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

3∣3⇒3∣32

ต่อไปเป็นขั้นอุปนัย จะเห็นว่าลำดับ ai เขียนได้เป็น 3n เมื่อ n เป็นจำนวนนับ นั่นคือสมาชิกแต่ละตัวมากกว่าตัวก่อนหน้าอยู่สาม ทีนี้สมมติว่านิพจน์เป็นจริงสำหรับ n และต้องแสดงว่าเป็นจริงสำหรับ (n + 3) ด้วย ซึ่งเป็นกฎที่ให้สมาชิกตัวถัดไปในลำดับที่เราพิจารณา เขียนสมมติฐานการอุปนัยก่อน:

3∣n⇒3∣n2

แล้วเขียนสิ่งที่ต้องการพิสูจน์

3∣(n+3)⇒3∣(n+3)2

กระจายวงเล็บอีกข้างหนึ่งด้วยสูตร:

3∣(n+3)⇒3∣n2+6n+9

ใกล้ถึงเป้าหมายแล้ว ข้างซ้ายมีนิพจน์ที่หารด้วยสามลงตัวแน่นอน เพราะตามข้อสมมติ n หารด้วยสามลงตัว (เราพิจารณาเฉพาะจำนวนในลำดับ ai) และสามก็หารด้วยสามลงตัว ข้างขวามี n2 ก่อน ซึ่งหารด้วยสามลงตัวตามสมมติฐานการอุปนัย เพราะเรารู้ว่า n หารด้วยสามลงตัว และสมมติฐานการอุปนัยบอกว่าถ้า n หารด้วยสามลงตัว แล้ว n2 ก็หารด้วยสามลงตัวด้วย:

3∣n⇒3∣n2

ต่อไปคือนิพจน์ 6n ซึ่งหารด้วยสามลงตัวอย่างเห็นได้ชัด นึกภาพเป็นการตัดทอนเศษส่วนก็ได้:

6n3=2n

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

จำนวนวงเล็บในนิพจน์

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

  • จำนวนนับ
  • ถ้า p เป็นนิพจน์อย่างง่าย แล้ว (p2) ก็เป็นนิพจน์อย่างง่าย
  • ถ้า p และ q เป็นนิพจน์อย่างง่าย แล้ว (p + q) ก็เป็นนิพจน์อย่างง่าย

ตัวอย่างนิพจน์อย่างง่าย: 12 54 (5 + 6) (12 + 7) (62) และ ((5 + 6)2) ส่วนต่อไปนี้ไม่ใช่นิพจน์อย่างง่าย:

  • 1 + 2 → ขาดวงเล็บด้านนอก
  • (1 + 2 → ขาดวงเล็บปิด
  • 132 → ขาดวงเล็บด้านนอก
  • (1 + 2 + 3) → ขาดวงเล็บ ที่ถูกต้องควรเขียนเป็น (1 + (2 + 3))

นิพจน์อย่างง่ายอาจเกิดขึ้น เช่น ดังนี้ เริ่มจากเลือกนิพจน์อย่างง่าย (a + b) แทน a ด้วยนิพจน์อย่างง่าย a = (c + d) จะได้ ((c + d) + b) แล้วแทน b ด้วยสาม: ((c + d) + 3) แทน c ด้วยสิบ: ((10 + d) + 3) และสุดท้ายแทน d ด้วย (52): ((10 + (52)) + 3) ต้องรักษาวงเล็บไว้ให้ครบ มิฉะนั้นจะใช้ไม่ได้

ต่อไปจะพิสูจน์ว่านิพจน์อย่างง่ายมีวงเล็บเป็นจำนวนคู่ (ศูนย์ก็เป็นจำนวนคู่)

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

j=n;n∈N

นิพจน์ j มีวงเล็บเป็นศูนย์ สมาชิกตัวแรกจึงเป็นไปตามข้อความ ในขั้นอุปนัยจะสมมติว่ามีนิพจน์อย่างง่ายสองนิพจน์ p และ q ซึ่งมีวงเล็บเป็นจำนวนคู่ทั้งคู่ แล้วต้องพิสูจน์ว่านิพจน์อย่างง่าย (p + q) และ (p2) ก็มีวงเล็บเป็นจำนวนคู่ด้วย

เริ่มจากการบวก นิยามฟังก์ชัน z(q) ซึ่งให้จำนวนวงเล็บของนิพจน์ q จะได้ว่านิพจน์ (p + q) มีวงเล็บ z(p) + z(q) + 2 อัน คือมีวงเล็บมากกว่าผลบวกของจำนวนวงเล็บของนิพจน์ p และ q อยู่สองอัน ตามสมมติฐานการอุปนัย ทั้ง z(p) และ z(q) เป็นจำนวนคู่ เมื่อบวกจำนวนคู่สามจำนวนก็ได้จำนวนคู่อีก ข้อความจึงเป็นจริงในกรณีนี้

ต่อไปเป็นเลขยกกำลัง สมมติฐานการอุปนัยยังคงเป็นจริง คือนิพจน์อย่างง่าย p มีวงเล็บเป็นจำนวนคู่ นิพจน์ (p2) จึงมีวงเล็บ z(p) + 2 อัน คือมากกว่านิพจน์ p อยู่สองอันอีกเช่นกัน ในกรณีนี้ก็บวกจำนวนคู่เข้าด้วยกัน ผลลัพธ์จึงเป็นจำนวนคู่

ข้อความเป็นจริงสำหรับสมาชิกตัวแรกและเป็นจริงในขั้นอุปนัย ข้อความนี้จึงเป็นจริง

สารบัญ: การพิสูจน์คืออะไร, การพิสูจน์โดยข้อขัดแย้ง, อุปนัยเชิงคณิตศาสตร์