Chứng minh dùng phương pháp quy nạp thế nào năm 2024
|
Nhà toán học vĩ đại Euclid đã viết "Trong thực tế, nhiều tính chất của các số đã biết đều được tìm ra bằng phép quy nạp và được tìm thấy rất lâu trước khi sự đúng đắn của chúng được chứng minh chặt chẽ. Cũng có rất nhiều tính chất quen thuộc với chúng ta nhưng hiện thời chúng ta còn chưa chứng minh được. Chỉ có con đường quan sát và tư duy quy nạp mới có thể dẫn chúng ta đến chân lý." Câu nói này đã phần nào lột tả được tầm quan trọng của phép quy nạp trong cuộc sống, khoa học và toán học. Tuy nhiên, quá trình quy nạp là quá trình đi từ "tính chất" của một số cá thể suy ra "tính chất" của tập thể nên không phải lúc nào cũng đúng. Phép suy luận này chỉ đúng khi thỏa mãn những điều kiện nhất định. Trong toán học cũng vậy, quá trình suy luận này chỉ đúng khi nó thỏa mãn nguyên lý quy nạp. Để chứng minh một mệnh đề đúng với mọi \(n \in {N^*}\) bằng phương pháp quy nạp toán học, ta thực hiện các bước sau: Bước 1: Kiểm tra mệnh đề đúng với \(n = 1\). Bước 2: Giả sử mệnh đề đúng với \(n = k \ge 1\) (giả thiết quy nạp). Bước 3: Cần chứng minh mệnh đề đúng với \(n = k + 1\) Chú ý: Trong trường hợp chứng minh một mệnh đề đúng với mọi số tự nhiên \(n \ge p\) (p là số tự nhiên) thì thuật toán là: Quy nạp toán học là một phương pháp chứng minh toán học dùng để chứng minh một mệnh đề về bất kỳ tập hợp nào được xếp theo thứ tự. Thông thường nó được dùng để chứng minh mệnh đề áp dụng cho tập hợp tất cả các số tự nhiên. Quy nạp toán học là một hình thức chứng minh trực tiếp, thường được thực hiện theo hai bước. Khi cố gắng để chứng minh một mệnh đề là đúng cho tập hợp các số tự nhiên, bước đầu tiên, được gọi là bước cơ sở, là chứng minh mệnh đề đưa ra là đúng với số tự nhiên đầu tiên. Bước thứ hai, được gọi là bước quy nạp, là chứng minh rằng, nếu mệnh đề được giả định là đúng cho bất kỳ số tự nhiên nào đó, thế thì nó cũng đúng cho số tự nhiên tiếp theo. Sau khi chứng minh hai bước này, các quy tắc suy luận khẳng định mệnh đề là đúng cho tất cả các số tự nhiên. Trong thuật ngữ phổ biến, sử dụng phương pháp nói trên được gọi là sử dụng nguyên lý quy nạp toán học. Phương pháp này có thể được mở rộng để chứng minh các mệnh đề về các cấu trúc được thiết lập tổng quát hơn, chẳng hạn như cây; quá trình tổng quát này, được gọi là quy nạp cấu trúc, được sử dụng trong logic toán và khoa học máy tính. Quy nạp toán học theo nghĩa mở rộng này có quan hệ chặt chẽ với đệ quy. Quy nạp toán học, trong một số hình thức, là nền tảng của tất cả các phép chứng minh tính đúng đắn của các chương trình máy tính. Mặc dù tên của nó là gần giống với lập luận quy nạp, quy nạp toán học không được nhầm lẫn như là một phương pháp của lập luận quy nạp. Quy nạp toán học là một quy tắc suy luận được sử dụng trong chứng minh. Trong toán học, chứng minh bao gồm những phép sử dụng quy nạp toán học là những ví dụ của suy diễn logic, và các lập luận quy nạp bị loại ra khỏi phép chứng minh. Mô tả[sửa | sửa mã nguồn]Hình thức đơn giản và phổ biến nhất của phương pháp quy nạp toán học suy luận rằng một mệnh đề liên quan đến một số tự nhiên n cũng đúng với tất cả các giá trị của n. Cách chứng minh bao gồm hai bước sau:
Việc n = 0 hay n = 1 phụ thuộc vào định nghĩa của số tự nhiên. Nếu 0 được coi là một số tự nhiên, bước cơ sở được đưa ra bởi n = 0. Nếu, mặt khác, 1 được xem như là số tự nhiên đầu tiên, bước hợp cơ sở được đưa ra với n = 1. Ví dụ[sửa | sửa mã nguồn]Quy nạp toán học có thể được sử dụng để chứng minh rằng mệnh đề P(n) sau, đúng với tất cả số tự nhiên n.
P(n) đưa ra một công thức cho tổng các số tự nhiên nhỏ hơn hoặc bằng số n. Cách chứng minh P(n) đúng với mỗi số tự nhiên n như sau. Quy nạp và đệ quy là hai khái niệm cực kì quan trọng trong toán học và trong tin học. Vì vậy nắm rõ được bản chất về mặt kiến thức, về mặt phương pháp cũng như tư duy là điều bất cứ ai trong chúng ta đều mong muốn hướng tới. Thêm vào đó, khá nhiều bạn trong chúng ta còn cho rằng, bản chất của phép quy nạp chính là phép đệ quy đòi hỏi phép quy nạp. Về mặt định nghĩa, người ta cho rằng, quy nạp là kết luận đi từ trường hợp riêng đi tới trường hợp tổng quát. Nghĩa là, kết luận tổng quát dựa trên việc nghiên cứu các tính chất của nhiều sự kiện, nhiều thí nghiệm hay nhiều quan sát riêng lẻ. Nếu kết luận chung dựa vào nghiên cứu tất cả các sự kiện riêng (các đối tượng, các hình, các số, vv…) thì quy nạp được gọi là đầy đủ hay hoàn chỉnh. Nếu kết luận chung dựa vào nghiên cứu một phần của tâp hợp tất cả các sự kiện (các đối tượng) thì quy nạp được gọi là không đầy đủ hay không hoàn chỉnh. Trong nhiều lĩnh vực khác nhau của Toán học ( số học, hình học, giải tích...) ta thường gặp những bài toán với yêu cầu chứng minh mệnh đề chứa biến P(n) là một mệnh đề đúng với mọi giá trị nguyên dương của biến n. Ví d ụ 1: Chứng minh rằng với mọi số nguyên dương n, ta luôn có: G iải: (1) Ta thấy (1) đúng khi n=1. (2) Ta sẽ chứng minh khẳng định sau: "Với k là một số nguyên dương tùy ý, nếu (1) đúng với n=k thì nó cũng đúng với n=k+1" (3). Thật vậy: Nếu (1) đúng với n=k tức là: Suy ra: , tức là (1) đúng với n=k+1. Từ (2) và (3) ta suy ra (1) đúng với mọi giá trị nguyên dương của n. Một cách khái quát, để chứng minh mệnh đề chứa biến P(n) là một mệnh đề đúng với mọi giá trị nguyên dương của n, ta thực hiện hai bước sau: Bước1:( bước cơ sở hay bước mở đầu) Chứng minh P(n) đúng khi n=1. Bước2:( bước quy nạp hay bước di truyền) Với k là một số nguyên dương, xuất phát từ giả thiết ( được gọi là giả thiết quy nạp) P(n) đúng với n=k, ta chứng minh P(n) cũng là mệnh đề đúng với n=k+1. Ta có thể kết luận: [P(1) ∧ ∀n(P(n) → P(n 1))] → ∀nP(n). Chú ý rằng khi chúng ta sử dụng quy nạp toán học để chứng minh, đầu tiên chúng ta chỉ ra rằng P(1) là đúng. Khi đó chúng biết rằng P(2) là đúng, bởi vì P(1) đã ngầm dẫn tới P(2). Hơn nữa, chúng ta cũng chỉ ra được P(3) là đúng vì P(2) đã ngầm dẫn tới P(3). Tiếp tục như vậy P(k) là đúng cho bất kỳ số nguyên dương k nào. Chú ý thêm rằng trong chứng minh quy nạp chúng ta không giả định là P(n) đúng với mọi số nguyên dương! Đó chỉ là việc giả định rằngnếuP(n)màđúngthìP(n+1)cũng đúng. Một minh họa hình thức cho quy nập toán học có thể hình ảnh hóa bằng hiệu ứng đổ của các quân domino. Tạisaochứngminhquynạplàđúng?Kỹ thuật chứng minh quy nạp dựa trên cơ sở lập luận chính xác. Giả sử chúng ta đã có P(1) là đúng và mệnh đề P(n)→P(n+1) là đúng cho mọi số nguyên n. Để chỉ ra P(n) đúng cho mọi số nguyên dương, giả định có ít nhất một số P(n) là sai. Thì khi đó tập S gồm các số nguyên dương để P(n) sai là khác rỗng. Từ đó ta kết luận S có ít nhất 1 phần tử, trong các phần tử sai đó ta chọn một phần tử, chúng ta ký hiệu là k sao cho P(k) sai còn P(k-1) đúng (chúng ta luôn chọn được k như vậy nếu không thì sao? Sinh viên có thể chứng minh điều này? ). Rõ ràng rằng k khác 1, bởi vì P(1) là đúng (đã được kiểm tra). Bởi vì k dương và lớn hơn 1 nên k-1 nguyên dương. Hơn nữa k-1 nhỏ hơn k, và k-1 không nằm trong tập S nên P(k-1) đúng. Phép kéo theo P(k-1)→P(k) đúng, mà P(k-
vậy, P(n) đúng cho mọi số nguyên dương n. M ột s ố ví d ụ về p h ư ơ n g ph á p c h ứ n g m i n h q u y n ạ p. Vídụ2:CMR với , ta luôn có: (4) Giải: Bước 1: Dễ thấy (4) đúng với n=1. Bước 2: Giả sử (4) đúng với , tức là: Ta CM (4) cũng đúng với n=k+1, tức là: Thật vậy, từ giả thiết quy nạp, ta có: Vậy (4) đúng với Tương tự, hãy CM: Vídụ3:CMR với mọi số nguyên dương , ta luôn có: Giải Bước 1: Với n=3, dễ thấy (5) đúng Bước 2: Giả sử (5) đúng khi , tức là: Vậy (5) đúng với mọi số nguyên dương Vídụ4.Chứng minh rằng với mọi số nguyên đồng (tiền Việt Nam) lớn hơn 6 có thể đổi ra tiền lẻ không dư bằng những đồng tiền gồm những tờ 2 đồng và 5 đồng (1 đồng ở đây bằng 1000 đồng trong thực tế). Lờigiải.Đẳng thức sau đây nói lên với 7 đồng, 8 đồng thì gồm tờ 2 đồng và 5 đồng như thế nào: 7 = 5 + 2; 8 = 2 + 2 + 2 +2. Nếu ta thêm vào hai vế của các đẳng thức trên tờ 2 đồng, thì 9 = 7 + 2; 10 = 8 + 2. Tiếp tục thêm 2 đồng vào hai đẳng thức sau cùng, ta có 11 = 9 + 2; 12 = 10 +2. Ta còn tiếp tục được cho bất cứ số nguyên nào. Ta thấy rằng ở bước trước có hai đẳng thức và suy ra bước sau có hai đẳng thức. Như vậy với mọi số n nguyên đồng nào dù là số chẵn hoặc số lẻ khi n-2 cũng rơi vào một trong hai trường hợp trước đó đã đổi được ra hai loại tiền 2 đồng và 5 đồng. Suy ra nó cũng đổi thành các đồng 2 đồng và 5 năm. Như vậy, khẳng định của của mệnh đề là đúng. Vídụ5.Tính tổng n số tự nhiên đầu tiên. Lời giải. Kí hiệu P(n) là tổng phải tìm, nghĩa là P(n) = 1 + 2 + 3 + ... + n. Ta tính một số tổng tại những giá trị ban đầu: N 1 2 3 4 5 6 7 P(n) 1 3 6 10 15 21 28 Ta 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 ở hàng dưới. Như 1.2 = 2.1, 2.3 = 2.3, 3.4 = 2.6, 4.5 = 2.10, 5.6 \=2.15, 6.7 = 2. 21, ... Như vậy ta có thể dự đoán công thức phải tìm là (1) Biểu thức trên được gọi là giả thiết quy nạp. Muốn chắc chắn công thức này đúng ta phải chứng minh bằng phương pháp quy nạp thông qua hai bước: 1. Bước cơ sở: Với n = 1 công thức (1) đúng như cách tính ở trên. 2. Bước quy nạp: Giả sử n = k, P(k) đúng, nghĩa là đã có Ta phải chứng minh (1) cũng đúng cho n = k + 1. Thật vậy, Do đó công thức (1) cũng đúng với n = k +1, theo nguyên lí quy nạp toán học công thức (1) đúng với mọi mọi n > 0. Cách c h ứ ng m i n h b ằng ph ư ơ ng pháp quy n ạp toán h ọ c c ần thi ế t th ứ c hiện hai b ư ớ c như phân tích ở ph ầ n t r ên. N h ư ng khó kh ă n c h ủ yếu l à t r ong b ư ớ c q uy n ạp toán học là khi m ệnh đề g i ả s ử đ ã đúng cho P(k) p h ải ch ứ ng m inh cho P(k + 1). T h ư ờ ng ng ư ờ i ta t ì m m ối l i ên hệ gi ữ a P(k) v à P(k + 1) đ ể s uy r a k ết quả phải ch ứ ng m inh. |
