phải|nhỏ|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.

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ả

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:

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)

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.

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

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: :$1\; =\; \backslash frac\{1\backslash cdot(1\; +\; 1)\}\{2\}\backslash ,.$ Ở 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, 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 cũng đúng: :$(0\; +\; 1\; +\; 2\; +\; \backslash cdots\; +\; k)+\; (k+1)\; =\; \backslash 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:

:$\backslash frac\{k(k\; +\; 1)\}\{2\}\; +\; (k+1)\backslash ,.$

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

Vì vậy 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