การเหนี่ยวนำทางคณิตศาสตร์

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

คำจำกัดความ

Mathematical Induction เป็นเทคนิคทางคณิตศาสตร์ที่ใช้ในการพิสูจน์คำสั่งสูตรหรือทฤษฎีบทเป็นจริงสำหรับจำนวนธรรมชาติทุกตัว

เทคนิคนี้เกี่ยวข้องกับสองขั้นตอนในการพิสูจน์คำแถลงดังที่ระบุไว้ด้านล่าง -

Step 1(Base step) - พิสูจน์ได้ว่าคำสั่งนั้นเป็นจริงสำหรับค่าเริ่มต้น

Step 2(Inductive step)- มันพิสูจน์ให้เห็นว่าถ้าคำสั่งที่เป็นจริงสำหรับเอ็น^THซ้ำ (หรือจำนวนn ) แล้วมันยังเป็นจริงสำหรับ(n + 1) ^THซ้ำ (หรือหมายเลข1 + n )

ทำอย่างไร

Step 1- พิจารณาค่าเริ่มต้นที่ข้อความนั้นเป็นจริง มันจะแสดงให้เห็นว่าคำสั่งเป็นจริงสำหรับ n = ค่าเริ่มต้น

Step 2- สมมติคำสั่งที่เป็นจริงสำหรับค่าของn = k แล้วพิสูจน์คำสั่งที่เป็นจริงสำหรับn = k + 1 เราแบ่งn = k + 1ออกเป็นสองส่วนส่วนหนึ่งคือn = k (ซึ่งพิสูจน์แล้ว) และพยายามพิสูจน์อีกส่วนหนึ่ง

ปัญหา 1

$ 3 ^ n-1 $ คือผลคูณของ 2 สำหรับ n = 1, 2, ...

Solution

Step 1 - สำหรับ $ n = 1, 3 ^ 1-1 = 3-1 = 2 $ ซึ่งเป็นผลคูณของ 2

Step 2 - ให้เราถือว่า $ 3 ^ n-1 $ เป็นจริงสำหรับ $ n = k $ ดังนั้น $ 3 ^ k -1 $ จึงเป็นจริง (เป็นสมมติฐาน)

เราต้องพิสูจน์ว่า $ 3 ^ {k + 1} -1 $ เป็นผลคูณของ 2 ด้วย

$ 3 ^ {k + 1} - 1 = 3 \ คูณ 3 ^ k - 1 = (2 \ คูณ 3 ^ k) + (3 ^ k - 1) $

ส่วนแรก $ (2 \ คูณ 3k) $ แน่นอนว่าจะเป็นผลคูณของ 2 และส่วนที่สอง $ (3k -1) $ ก็เป็นจริงเช่นกันตามสมมติฐานก่อนหน้าของเรา

ดังนั้น $ 3 ^ {k + 1} - 1 $ จึงเป็นผลคูณของ 2

ดังนั้นจึงพิสูจน์ได้ว่า $ 3 ^ n - 1 $ เป็นผลคูณของ 2

ปัญหา 2

$ 1 + 3 + 5 + ... + (2n-1) = n ^ 2 $ สำหรับ $ n = 1, 2, \ dots $

Solution

Step 1 - สำหรับ $ n = 1, 1 = 1 ^ 2 $ ดังนั้นจึงพอใจขั้นตอนที่ 1

Step 2 - ให้เราถือว่าคำสั่งนั้นเป็นจริงสำหรับ $ n = k $

ดังนั้น $ 1 + 3 + 5 + \ dots + (2k-1) = k ^ 2 $ จึงเป็นจริง (เป็นสมมติฐาน)

เราต้องพิสูจน์ว่า $ 1 + 3 + 5 + ... + (2 (k + 1) -1) = (k + 1) ^ 2 $ ถือด้วย

$ 1 + 3 + 5 + \ dots + (2 (k + 1) - 1) $

$ = 1 + 3 + 5 + \ dots + (2k + 2 - 1) $

$ = 1 + 3 + 5 + \ dots + (2k + 1) $

$ = 1 + 3 + 5 + \ dots + (2k - 1) + (2k + 1) $

$ = k ^ 2 + (2k + 1) $

$ = (k + 1) ^ 2 $

ดังนั้น $ 1 + 3 + 5 + \ dots + (2 (k + 1) - 1) = (k + 1) ^ 2 $ ค้างไว้ซึ่งตรงตามขั้นตอนที่ 2

ดังนั้น $ 1 + 3 + 5 + \ dots + (2n - 1) = n ^ 2 $ จึงได้รับการพิสูจน์แล้ว

ปัญหา 3

พิสูจน์ว่า $ (ab) ^ n = a ^ nb ^ n $ เป็นจริงสำหรับทุกจำนวนธรรมชาติ $ n $

Solution

Step 1 - สำหรับ $ n = 1, (ab) ^ 1 = a ^ 1b ^ 1 = ab $ ดังนั้นจึงพอใจขั้นตอนที่ 1

Step 2 - ให้เราถือว่าคำสั่งนั้นเป็นจริงสำหรับ $ n = k $ ดังนั้น $ (ab) ^ k = a ^ kb ^ k $ จึงเป็นจริง (เป็นสมมติฐาน)

เราต้องพิสูจน์ว่า $ (ab) ^ {k + 1} = a ^ {k + 1} b ^ {k + 1} $ ถือด้วย

ระบุ$ (ab) ^ k = a ^ kb ^ k $

หรือ$ (ab) ^ k (ab) = (a ^ kb ^ k) (ab) $ [คูณทั้งสองข้างด้วย 'ab']

หรือ$ (ab) ^ {k + 1} = (aa ^ k) (bb ^ k) $

หรือ$ (ab) ^ {k + 1} = (a ^ {k + 1} b ^ {k + 1}) $

ดังนั้นขั้นตอนที่ 2 จึงได้รับการพิสูจน์แล้ว

ดังนั้น$ (ab) ^ n = a ^ nb ^ n $เป็นจริงสำหรับทุกจำนวนธรรมชาติ n

การเหนี่ยวนำที่แข็งแกร่ง

การเหนี่ยวนำที่แข็งแกร่งเป็นอีกรูปแบบหนึ่งของการอุปนัยทางคณิตศาสตร์ ด้วยเทคนิคการเหนี่ยวนำนี้เราสามารถพิสูจน์ได้ว่าฟังก์ชันเชิงประพจน์ $ P (n) $ เป็นจริงสำหรับจำนวนเต็มบวกทั้งหมด $ n $ โดยใช้ขั้นตอนต่อไปนี้ -

• Step 1(Base step) - พิสูจน์ได้ว่าโจทย์เริ่มต้น $ P (1) $ จริง

• Step 2(Inductive step) - พิสูจน์ได้ว่าคำสั่งเงื่อนไข $ [P (1) \ land P (2) \ land P (3) \ land \ dots \ land P (k)] → P (k + 1) $ เป็นจริงสำหรับจำนวนเต็มบวก $ k $.