Phương pháp quy nạp toán học

Quy nạp toán học là một kỹ thuật chứng minh dùng trong toán học để khẳng định một mệnh đề cho bất kỳ tập hợp nào theo thứ tự. Thường thì nó được áp dụng để chứng minh mệnh đề đúng cho tất cả các số tự nhiên.

Quy nạp toán học là phương pháp chứng minh trực tiếp, thường có hai bước. Đầu tiên là bước cơ sở, chứng minh mệnh đề đúng với số tự nhiên đầu tiên. Sau đó là bước quy nạp, chứng minh nếu mệnh đề đúng với một số tự nhiên nào đó, thì cũng đúng với số tự nhiên kế tiếp. Sau khi hoàn thành hai bước này, ta có thể kết luận mệnh đề đúng với tất cả các số tự nhiên, hay gọi là nguyên lý quy nạp toán học.

Phương pháp này còn có thể mở rộng để chứng minh các mệnh đề về các cấu trúc tổng quát hơn, như cây; quá trình này gọi là quy nạp cấu trúc, được sử dụng trong logic toán học và khoa học máy tính. Quy nạp toán học theo nghĩa rộng có liên quan chặt chẽ với đệ quy và là nền tảng của các phương pháp chứng minh tính đúng đắn của chương trình máy tính.

Dù tên gọi có thể gây nhầm lẫn với lập luận quy nạp, quy nạp toán học không phải là một phương pháp lập luận quy nạp. Đây là một quy tắc suy luận được dùng trong chứng minh. Trong toán học, các chứng minh sử dụng quy nạp toán học là những ví dụ của suy luận logic, và lập luận quy nạp không được xem là chứng minh.

Mô tả

Hình thức phổ biến và đơn giản nhất của quy nạp toán học cho 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. Quá trình chứng minh bao gồm hai bước:

1. Bước cơ sở: chứng minh mệnh đề đúng với số tự nhiên đầu tiên n. Thường thì n = 0 hoặc n = 1, hiếm khi n = -1 (mặc dù không phải là số tự nhiên, mở rộng định nghĩa cho -1 vẫn có thể áp dụng).
2. Bước quy nạp: chứng minh rằng nếu mệnh đề đúng với một số tự nhiên n nào đó, thì cũng đúng với n + 1. Giả định ở bước quy nạp rằng mệnh đề đúng với số n được gọi là giả thiết quy nạp. Để thực hiện bước này, cần giả định giả thiết quy nạp là đúng và dùng nó để chứng minh mệnh đề cho n + 1.

Việc chọn 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à số tự nhiên, bước cơ sở sẽ là n = 0. Nếu ngược lại, 1 được xem là số tự nhiên đầu tiên, thì bước cơ sở sẽ là n = 1.

Ví dụ

Quy nạp toán học có thể được áp dụng để chứng minh rằng mệnh đề P(n) sau đúng với mọi số tự nhiên n.

$0+1+2+\cdots <!--\; \cdots \; -->+n=\frac{n(n+1)}{2}.$

P(n) là công thức tính tổng các số tự nhiên từ 0 đến n. Cách chứng minh P(n) đúng với mọi số tự nhiên n như sau.

Bước cơ sở: Chứng minh rằng mệnh đề đúng với n = 1.
Ta có P(1) là:

$1=\frac{1\cdot <!--\; \cdot \; -->(1+1)}{2}.$

Vế trái của phương trình là 1, và như vậy bằng 1. Vế phải là 1·(1 + 1)/2 = 1. Hai vế bằng nhau, do đó mệnh đề đúng với n=1. Vậy nên P(1) đúng.

Bước quy nạp: Chứng minh rằng nếu P (k) đúng, thì P(k + 1) cũng đúng. Điều này được thực hiện như sau.

Giả sử P(k) đúng (với một số tự nhiên k). Ta cần chứng minh rằng P(k + 1) cũng đúng:

$(0+1+2$

+ ⋯ + k ) + ( k + 1 ) = ( k + 1 ) ( ( k + 1 ) + 1 ) 2 . {\displaystyle (0+1+2+\cdots +k)+(k+1)={\frac {(k+1)((k+1)+1)}{2}}.}

Áp dụng giả thuyết quy nạp rằng P(k) là đúng, vế trái có thể được viết lại thành:

$\frac{k(k+1)}{2}+(k+1).$

Có thể biến đổi như sau:

Vậy nên P(k + 1) cũng là đúng.

Do đã chứng minh cả bước cơ sở và bước quy nạp, ta kết luận rằng mệnh đề P(n) đúng với mọi số tự nhiên n.

• Đệ quy
• Quy nạp cấu trúc
• Quy nạp siêu hạn

Tài liệu tham khảo

Lời mở đầu

• Franklin, J.; A. Daoud (2011). Proof in Mathematics: An Introduction. Sydney: Kew Books. ISBN 0-646-54509-4. (Ch. 8.)
• Hazewinkel, Michiel biên tập (2001), “Mathematical induction”, Bách khoa toàn thư Toán học, Springer, ISBN 978-1-55608-010-4
• Hermes, Hans (1973). Introduction to Mathematical Logic. Hochschultext. London: Springer. ISBN 3540058192. ISSN 1431-4657.
• Knuth, Donald E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (ấn bản 3). Addison-Wesley. ISBN 0-201-89683-4. (Phần 1.2.1: Mathematical Induction, tr. 11–21.)
• Kolmogorov, Andrey N.; Sergei V. Fomin (1975). Introductory Real Analysis. Silverman, R. A. (dịch, biên tập). New York: Dover. ISBN 0-486-61226-0. (Phần 3.8: Quy nạp siêu hạn, tr. 28–29.)

Lịch sử

• Acerbi, F. (2000). “Plato: Parmenides 149a7-c3. Một Chứng Minh Bằng Quy Tắc Toàn Bộ?”. Tạp Chí Lịch Sử Khoa Học Chính Xác. 55: 57–76. doi:10.1007/s004070000020.
• Bussey, W. H. (1917). “Nguồn Gốc Của Quy Tắc Toán Học”. Tạp Chí Toán Học Mỹ. 24 (5): 199–207. doi:10.2307/2974308. JSTOR 2974308.
• Cajori, Florian (1918). “Nguồn Gốc Của Tên 'Quy Tắc Toán Học'”. Tạp Chí Toán Học Mỹ. 25 (5): 197–201. doi:10.2307/2972638. JSTOR 2972638.
• Fowler D. (1994). “Người Hy Lạp Có Thể Đã Sử Dụng Quy Tắc Toán Học? Họ Có Sử Dụng Nó?”. Physis. XXXI: 253–265.
• Freudenthal, Hans (1953). “Về Lịch Sử Của Quy Tắc Toàn Bộ”. Tạp Chí Quốc Tế Về Lịch Sử Khoa Học. 6: 17–37.
• Katz, Victor J. (1998). Lịch Sử Toán Học: Một Giới Thiệu. Addison-Wesley. ISBN 0-321-01618-1.
• Peirce, C. S. (1881). “Về Logic Của Số”. Tạp Chí Toán Học Mỹ. 4 (1–4). tr. 85–95. doi:10.2307/2369151. JSTOR 2369151. MR 1507856. In lại (CP 3.252-88), (W 4:299-309).
• Rabinovitch, Nachum L. (1970). “Rabbi Levi Ben Gershon và Nguồn Gốc Của Quy Tắc Toán Học”. Tạp Chí Lịch Sử Khoa Học Chính Xác. 6 (3): 237–248. doi:10.1007/BF00327237.
• Rashed, Roshdi (1972). “Quy Tắc Toán Học: al-Karajī, as-Samaw'al”. Tạp Chí Lịch Sử Khoa Học Chính Xác (bằng tiếng Pháp). 9 (1): 1–21. doi:10.1007/BF00348537.
• Shields, Paul (1997). “Làm Mới Hóa Học Toán Của Peirce”. Trong Houser; và đồng nghiệp (biên tập). Nghiên Cứu Về Logic Của Charles S. Peirce.
• Unguru, S. (1991). “Toán Học Hy Lạp Và Quy Tắc Toán Học”. Physis. XXVIII: 273–289.
• Unguru, S. (1994). “Theo Dõi Quy Tắc Toán Học”. Physis. XXXI: 267–272.
• Vacca, G. (1909). “Maurolycus, Người Đầu Tiên Phát Hiện Nguyên Tắc Quy Tắc Toán Học”. Tạp Chí Toán Học Mỹ. 16 (2): 70–73. doi:10.1090/S0002-9904-1909-01860-9.
• Yadegari, Mohammad (1978). “Sử Dụng Quy Tắc Toán Học Của Abū Kāmil Shujā' Ibn Aslam (850-930)”. Isis. 69 (2): 259–262. doi:10.1086/352009. JSTOR 230435.