Mời các quý thầy cô và các em học sinh cùng tham khảo và tải về chi tiết tài liệu dưới đây
Phương pháp quy nạp toán học
CHƯƠNG I. NGUYÊN LÝ QUY NẠP TOÁN HỌC
1.1. Suy diễn và quy nạp
Để minh họa hai khái niệm rất hay gặp trong thực tế là suy diễn và quy nạp, ta lấy câu ca dao Việt Nam ai cũng biết:
“Số cô có mẹ có cha
Mẹ cô đàn bà cha cô đàn ông
Số cô có vợ có chồng
Sinh con đầu lòng chẳng gái thì trai”
Đây là câu đoán của ông thầy bói, ta đã biết thầy bói chỉ đoán mò thôi, nhưng ông thầy bói trong câu ca dao này rất khôn là dùng một khẳng định luôn luôn đúng “ai cũng có mẹ, có cha”. Từ đó dù áp dụng cho người đến bói cụ thể nào cũng đúng luôn, nghĩa là khẳng định riêng cũng đúng. Bước suy luận từ khẳng định chung áp dụng cho những khẳng định riêng biệt gọi là phép suy diễn. Phép suy diễn ở ví dụ trên là luôn đúng với hai câu đầu, nhưng có thể sai ở câu sau. Trong toán học rất hay dùng phép suy diễn, chẳng hạn, nếu hai góc trong của một tam giác đã cho là 300 và 700 , thì điều khẳng định sau đúng: “Góc thứ ba của tam giác đã cho là 800”. Mệnh đề chung ở đây là : “Tổng các góc trong một tam giác là 1800”.
Bây giờ ta đọc lại chuyện cười dân gian Việt Nam:
“Bốn ông thầy bói rủ nhau đi xem voi. Tới chỗ voi đứng, bốn thầy bói chen vào, sờ tận tay xem con voi nó thể nào. Về tới chợ, bốn thầy họp nhau bình phẩm.
Thầy sờ được cáo vòi voi nói:
Tưởng voi lạ lắm, té ra chỉ giống con đỉa cực lớn. Tôi sờ vào nó uốn cong người lại.
Thầy ôm phải cái chân, vội cãi: Voi chỉ hệt như cái cột nhà thôi. Tôi ôm vào vừa tay một cái cột cái.
Thầy nắm phải cái tai voi, chê: Các bác chỉ nói mò. Coi voi thật ra tựa như cái quạt to tướng.
Thầy túm phải cái đuôi voi,cười khẩy: Ba bác nói sai cả. Tôi đã túm nó trong tay, thì đúng là một cái chổi xể đại.
Không ai chịu ai, bốn thầy to tiếng cãi nhau ồn ào một góc chợ…”
Mỗi ông thầy bói đều dùng khẳng định riêng của mình để đoán, phát biểu khẳng định chung. Bước suy luận từ khẳng định riêng tiến tới phát biểu khẳng định chung được gọi là phép quy nạp. Khẳng định chung ở đây là “con vật đó là con voi”. Như vật 4 ông thầy bói đều phát biểu khẳng định chung sai. Chắc có một ông nào đó sáng mắt thì sẽ đúng. Ta thấy rằng phương pháp quy nạp có thể đưa đến kết quả nhận định sai. Phương pháp quy nạp rất hay được dùng trong nghiên cứu khoa học, nhất là toán học. Như vật chúng ta phải hiểu phương pháp quy nạp thế nào đây và áp dụng thế nào để nhận được mệnh đề khẳng định đúng.
1.2 Nguyên lý quy nạp toán học
Để ngắn gọn ta kí hiệu một khẳng định toán học là P(x), ở đây x là một biến số. Người ta thường đưa về dạng mệnh đề “Với mọi x (trong một tập S nào đó), P(x)”. Trong cuốn sách này ta lấy x = n là những số tự nhiên, S là tập các số tự nhiên (bao gồm toàn bộ các số nguyên dương). Ta sử dụng một tính chất rất quan trọng của tập số tự nhiên, thường người ta công nhận như một tiên đề (được gọi là tiên đề thứ tự).
Tiên đề: Trong mỗi tập hợp khác rỗng của những số tự nhiên có một phần tử nhỏ nhất.
Cho mỗi số tự nhiên n ứng với một khẳng định P(n). Ví dụ, với 1 ta cho tương ướng với khẳng định P(1): “số 1 là một số lẻ”, số 2 cho tương ứng với P(2): “số 2 là một số chẵn”; …Bằng phương pháp như vật chúng ta tạo ra dãy khẳng định riêng P(1), P(2), …, P(n), … Nguyên lý quy nạp toán học cho ta một phương pháp kiểm tra khẳng định P(n) đúng hoặc sai với mọi n. Nguyên lý quy nạp toán học được thể hiện qua định lý sau:
Định lý 1.1. Cho n0 là một số nguyên dương và P(n) là mệnh đề có nghĩa với mọi số tự nhiên n \[ \ge \] n0 . Nếu
A. P(n0) là đúng và
B. Nếu P(k) đúng, thì P(k + 1) cũng đúng với mỗi số tự nhiên k\[ \ge \]n0, khi đó mệnh đề P(n) đúng với mọi số tự nhiên n \[ \ge \]n0.
Chứng minh. Ta sẽ chứng minh bằng phản chứng. Giả sử ngược lại, mệnh đề khẳng định P(n) trong định lý 1.1 không đúng với một số tự nhiên n \[ \ge \]n0 nào đó. Nghĩa là tồn tại một số tự nhiên m \[ \ge \]n0 mà P(m) không đúng. Ta lấy số tự nhiên m nhỏ nhất mà P(m) không đúng (điều này thực hiện được do tiên đề thứ tự). Theo điều kiện A, ta có bất đẳng thức m \[ \ge \]n0, từ đó suy ra m – 1 \[ \ge \]n0. Từ bất đẳng thức vừa lập và chọn cách chọn số tự nhiên m suy ra P(m – 1) là đúng, nhưng nó không kéo theo được P(m) đúng cho số tiếp theo m = (m – 1) + 1. Điều này trái với giả thiết B.
Xuất phát từ mệnh đề khẳng định với các trường hợp riêng, chẳng hạn như các số 1, 2 hoặc 3 có thể nẩy sinh giả thiết mệnh đề đúng với mói số tự nhiên. Sau đó để chứng minh giả thiết của ta vừa xây dựng người ta lý luận theo nguyên lý quy nạp toán học. Phương pháp chứng minh như vậy gọi là phương pháp quy nạp toán học. Theo định lý trên phương pháp này gồm hai bước, thứ nhất ta kiểm tra khẳng định một tính chất với n = n0, gọi là bước cơ sở; sau đó chứng minh rằng nếu với mỗi k \[ \ge \]n0, P(k) thỏa mãn tính chất đã biết, thì suy ra P(k + 1) cũng có tính chất ấy, gọi là bước quy nạp. Kết luận là P(n) có tính chất đã cho với n \[ \ge \]n0. Cách chứng minh theo quy nạp toán học là tránh cho ta phải kiểm tra vô hạn bước các khẳng định của mệnh đề.
1.3. Giải đoạn quy nạp và giả thiết quy nạp
Phương pháp quy nạp toán học rất hay được áp dụng trong nghiên cứu và tìm tòi trong toán học, các ngành khoa học khác. Để hiểu cách áp dụng phương pháp quy nạp cho đầy đủ, ta xem xét một số ví dụ sau đây như một phép “suy luận có lý” mà G.Polya đã đề cập.
Ví dụ 1.1. Cho trước một số tự nhiên n. Hãy tìm tổng các số tự nhiên 1, 2, …, n.
Lời giải. Ta kí hiệu Sn là tổng phải tìm, nghĩa là Sn = 1 + 2 + … + n. (1.1)
Ta hi vọng là tìm ra công thức ngắn gọn để tính tổng trên, công thức đó giúp ta tính nhanh , gọn hơn là phải thực hiện lần lượt các phép cộng trong tổng. Ta cũng biết đây là cấp số cộng, nếu bạn đọc đã biết về cấp số này, thì ta có thể có ngay công thức tính tổng. Nhưng ở đây ta muốn minh họa quá trình áp dụng nguyên lý quy nạp toán học nên những điều đã biết về cấp số cộng ta bỏ qua, coi như chưa biết.
Ta tính tổng Sn từ đẳng thức (1.1) với một vài số tự nhiên liên tiếp, chẳng hạn bắt đầu từ 1. Những kết quả tính toán các trường hợp riêng ta xếp vào bảng
|
n |
1 |
2 |
3 |
4 |
5 |
6 |
|
Sn |
1 |
3 |
6 |
10 |
15 |
21 |
Mục đích của ta là tìm được quy luật chung (khẳng định chung), với bảng trên, mỗi số tự nhiên ở hàng trên trong bảng cho tương ứng với các số ở hàng dưới. Tìm ra quy luật của một bài toán phụ thuộc vào rất nhiều yếu tố: sự khéo léo trong quan sát; sự nhạy cảm dự đoán và kiểm tra của ta; từ các kinh nghiệm đã trải qua trong tính toán các bài toán tương tự, từ khả năng liên hệ bài toán tương tự với điều kiện mới,…
Trên bảng trên dễ thấy quy luật: Tích của hai số liên tiếp ở hàng trên bằng 2 lần số đầu tiên tương ứng ở hàng dưới. Thật vậy, 1.2 = 2.1, 2.3 = 2.3, 3.4 = 2.6, 5.6 = 2.15. Như vật giai đoạn quy nạp của chúng ta đã thành công: Tìm ra quy luật với các trường hợp riêng n = 1,2,3,4,5,6.
Tiếp tục một cách tự nhiên là mở rộng quy luật trên cho bảng số với các số tự nhiên bất kỳ. Ta đưa ra giả thiết thích hợp với quy luật vừa tìm được. Đặt \[1 + 2 + … + n = \frac{{n(n + 1)}}{2}\]. (1.2)
Một giả thiết ta đã làm như vật được gọi là giả thiết quy nạp. Nhưng câu hỏi đặt ra là đẳng thức (1.2) có đúng với mọi n = 1,2,… hay không? Rõ ràng nếu (1.2) đúng với mọi số tự nhiên thì bằng cách thay n bằng n + 1 chúng ta sẽ có đẳng thức \[1 + 2 + … + n + (n + 1) = \frac{{(n + 1)(n + 2)}}{2}\] (1.3)
Trái lại giả thiết (1.2) là đúng với mọi n = 1,2,…, nếu 1 nó đúng với n = 1 và 2 nó đúng với mỗi số k suy ra cũng đúng với cả k + 1. Điều này không có cách nào khác là phải áp dụng nguyên lý quy nạp toán học. Nghĩa là chúng ta phải kiểm tra những điều kiện A và B của định lý 1.1
Bước cơ sở: với n = 1, công thức (1.2) đúng (nó còn đúng cho cả n = 2,3,4,5,6).
Xem thêm