Quy nạp toán học

Quy nạp toán học có thể được minh họa mô phỏng bằng cách tham chiếu đến các tác dụng tuần tự của hiệu ứng domino.

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.^[1]

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.^[2]

Mô tả

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:

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

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ụ

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.

${\displaystyle 0+1+2+\cdots +n={\frac {n(n+1)}{2}}\,.}$

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.

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

${\displaystyle 1={\frac {1\cdot (1+1)}{2}}\,.}$

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

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

Giả sử P(k) đúng (với một số giá trị k). Sau đó phải chứng minh rằng P(k + 1) cũng đúng:

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

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

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

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

${\displaystyle {\begin{aligned}{\frac {k(k+1)}{2}}+(k+1)&={\frac {k(k+1)+2(k+1)}{2}}\\&={\frac {(k+1)(k+2)}{2}}\\&={\frac {(k+1)((k+1)+1)}{2}}\end{aligned}}}$

Vì vậy P(k + 1) cũng đúng.

Vì cả bước cơ sở và bước quy nạp đã được thực hiện, mệnh đề P(n) đúng với mọi số tự nhiên n

Xem thêm

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

Tham khảo

1. Anderson, Robert B. (1979). Proving Programs Correct. New York: John Wiley & Sons. tr. 1. ISBN 0471033952.
2. Suber, Peter. “Mathematical Induction”. Earlham College. Bản gốc lưu trữ ngày 24 tháng 5 năm 2011. Truy cập ngày 26 tháng 3 năm 2011.

Sách tham khảo

Giới thiệ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 thứ 3). Addison-Wesley. ISBN 0-201-89683-4. (Section 1.2.1: Mathematical Induction, pp. 11–21.)
• Kolmogorov, Andrey N.; Sergei V. Fomin (1975). Introductory Real Analysis. Silverman, R. A. (trans., ed.). New York: Dover. ISBN 0-486-61226-0. (Section 3.8: Transfinite induction, pp. 28–29.)

Lịch sử

• Acerbi, F. (2000). “Plato: Parmenides 149a7-c3. A Proof by Complete Induction?”. Archive for History of Exact Sciences. 55: 57–76. doi:10.1007/s004070000020.
• Bussey, W. H. (1917). “The Origin of Mathematical Induction”. The American Mathematical Monthly. 24 (5): 199–207. doi:10.2307/2974308. JSTOR 2974308.
• Cajori, Florian (1918). “Origin of the Name "Mathematical Induction"”. The American Mathematical Monthly. 25 (5): 197–201. doi:10.2307/2972638. JSTOR 2972638.
• Fowler D. (1994). “Could the Greeks Have Used Mathematical Induction? Did They Use It?”. Physis. XXXI: 253–265.
• Freudenthal, Hans (1953). “Zur Geschichte der vollständigen Induction”. Archives Internationales d'Histoire des Sciences. 6: 17–37.
• Katz, Victor J. (1998). History of Mathematics: An Introduction. Addison-Wesley. ISBN 0-321-01618-1.
• Peirce, C. S. (1881). “On the Logic of Number”. American Journal of Mathematics. 4 (1–4). tr. 85–95. doi:10.2307/2369151. JSTOR 2369151. MR 1507856. Reprinted (CP 3.252-88), (W 4:299-309).
• Rabinovitch, Nachum L. (1970). “Rabbi Levi Ben Gershon and the origins of mathematical induction”. Archive for History of Exact Sciences. 6 (3): 237–248. doi:10.1007/BF00327237.
• Rashed, Roshdi (1972). “L'induction mathématique: al-Karajī, as-Samaw'al”. Archive for History of Exact Sciences (bằng tiếng Pháp). 9 (1): 1–21. doi:10.1007/BF00348537.
• Shields, Paul (1997). “Peirce's Axiomatization of Arithmetic”. Trong Houser; và đồng nghiệp (biên tập). Studies in the Logic of Charles S. Peirce.
• Unguru, S. (1991). “Greek Mathematics and Mathematical Induction”. Physis. XXVIII: 273–289.
• Unguru, S. (1994). “Fowling after Induction”. Physis. XXXI: 267–272.
• Vacca, G. (1909). “Maurolycus, the First Discoverer of the Principle of Mathematical Induction”. Bulletin of the American Mathematical Society. 16 (2): 70–73. doi:10.1090/S0002-9904-1909-01860-9.
• Yadegari, Mohammad (1978). “The Use of Mathematical Induction by Abū Kāmil Shujā' Ibn Aslam (850-930)”. Isis. 69 (2): 259–262. doi:10.1086/352009. JSTOR 230435.