Quy nạp toán học
Mathematical induction, là một kỹ thuật để chứng minh kết quả hoặc thiết lập các câu lệnh cho các số tự nhiên. Phần này minh họa phương pháp này thông qua nhiều ví dụ.
Định nghĩa
Mathematical Induction là một kỹ thuật toán học được sử dụng để chứng minh một tuyên bố, một công thức hoặc một định lý là đúng với mọi số tự nhiên.
Kỹ thuật này bao gồm hai bước để chứng minh một tuyên bố, như được nêu dưới đây:
Step 1(Base step) - Nó chứng minh rằng một câu lệnh là đúng với giá trị ban đầu.
Step 2(Inductive step)- Điều đó chứng tỏ rằng nếu câu lệnh đúng với lần lặp thứ n (hoặc số n ) thì nó cũng đúng với lần lặp thứ (n + 1) (hoặc số n + 1 ).
Làm thế nào để làm nó
Step 1- Xem xét một giá trị ban đầu mà câu lệnh là đúng. Nó được chứng minh rằng câu lệnh đúng với n = giá trị ban đầu.
Step 2- Giả sử câu lệnh đúng với mọi giá trị của n = k . Sau đó, chứng minh mệnh đề là đúng với n = k + 1 . Chúng ta thực sự chia n = k + 1 thành hai phần, một phần là n = k (đã được chứng minh) và cố gắng chứng minh phần kia.
Vấn đề 1
$ 3 ^ n-1 $ là bội số của 2 cho n = 1, 2, ...
Solution
Step 1 - Với $ n = 1, 3 ^ 1-1 = 3-1 = 2 $ là bội số của 2
Step 2 - Giả sử $ 3 ^ n-1 $ đúng với $ n = k $, Do đó, $ 3 ^ k -1 $ là đúng (Đây là giả định)
Chúng ta phải chứng minh rằng $ 3 ^ {k + 1} -1 $ cũng là bội số của 2
$ 3 ^ {k + 1} - 1 = 3 \ lần 3 ^ k - 1 = (2 \ lần 3 ^ k) + (3 ^ k - 1) $
Phần đầu tiên $ (2 \ nhân 3k) $ chắc chắn là bội số của 2 và phần thứ hai $ (3k -1) $ cũng đúng như giả thiết trước của chúng ta.
Do đó, $ 3 ^ {k + 1} - 1 $ là bội số của 2.
Vì vậy, người ta chứng minh rằng $ 3 ^ n - 1 $ là bội của 2.
Vấn đề 2
$ 1 + 3 + 5 + ... + (2n-1) = n ^ 2 $ cho $ n = 1, 2, \ chấm $
Solution
Step 1 - Với $ n = 1, 1 = 1 ^ 2 $, Do đó, bước 1 được thỏa mãn.
Step 2 - Giả sử câu lệnh đúng với $ n = k $.
Do đó, $ 1 + 3 + 5 + \ dot + (2k-1) = k ^ 2 $ là đúng (Đó là một giả định)
Chúng ta phải chứng minh rằng $ 1 + 3 + 5 + ... + (2 (k + 1) -1) = (k + 1) ^ 2 $ cũng giữ
$ 1 + 3 + 5 + \ dấu chấm + (2 (k + 1) - 1) $
$ = 1 + 3 + 5 + \ dấu chấm + (2k + 2 - 1) $
$ = 1 + 3 + 5 + \ chấm + (2k + 1) $
$ = 1 + 3 + 5 + \ chấm + (2k - 1) + (2k + 1) $
$ = k ^ 2 + (2k + 1) $
$ = (k + 1) ^ 2 $
Vì vậy, $ 1 + 3 + 5 + \ dot + (2 (k + 1) - 1) = (k + 1) ^ 2 $ giữ thỏa mãn bước 2.
Do đó, $ 1 + 3 + 5 + \ dot + (2n - 1) = n ^ 2 $ được chứng minh.
Vấn đề 3
Chứng minh rằng $ (ab) ^ n = a ^ nb ^ n $ đúng với mọi số tự nhiên $ n $
Solution
Step 1 - Với $ n = 1, (ab) ^ 1 = a ^ 1b ^ 1 = ab $, Do đó, bước 1 được thỏa mãn.
Step 2 - Giả sử câu lệnh đúng với $ n = k $, Do đó, $ (ab) ^ k = a ^ kb ^ k $ đúng (Đó là một giả định).
Ta phải chứng minh rằng $ (ab) ^ {k + 1} = a ^ {k + 1} b ^ {k + 1} $ cũng giữ
Cho trước, $ (ab) ^ k = a ^ kb ^ k $
Hoặc, $ (ab) ^ k (ab) = (a ^ kb ^ k) (ab) $ [Nhân cả hai vế với 'ab']
Hoặc, $ (ab) ^ {k + 1} = (aa ^ k) (bb ^ k) $
Hoặc, $ (ab) ^ {k + 1} = (a ^ {k + 1} b ^ {k + 1}) $
Do đó, bước 2 đã được chứng minh.
Vì vậy, $ (ab) ^ n = a ^ nb ^ n $ đúng với mọi số tự nhiên n.
Cảm ứng mạnh
Cảm ứng mạnh là một dạng khác của quy nạp toán học. Thông qua kỹ thuật quy nạp này, chúng ta có thể chứng minh rằng một hàm mệnh đề, $ P (n) $ đúng với mọi số nguyên dương, $ n $, bằng cách sử dụng các bước sau:
Step 1(Base step) - Điều đó chứng tỏ mệnh đề ban đầu $ P (1) $ đúng.
Step 2(Inductive step) - Chứng minh rằng câu lệnh điều kiện $ [P (1) \ land P (2) \ land P (3) \ land \ dot \ land P (k)] → P (k + 1) $ đúng với các số nguyên dương $ k $.