MathLabs
Tiên đềĐã chứng minh

Nguyên lý quy nạp toán học

Phát biểu

Cho P(n)P(n) là một mệnh đề phụ thuộc số tự nhiên n≥n0n \ge n_0. Nếu (cơ sở quy nạp) P(n0)P(n_0) đúng, và (bước quy nạp) với mọi k≥n0k \ge n_0, P(k)P(k) đúng kéo theo P(k+1)P(k+1) đúng, thì P(n)P(n) đúng với mọi số nguyên n≥n0n \ge n_0.

Vì sao đúng?

Quy nạp giống như leo một chiếc thang vô hạn: nếu bạn có thể bước lên bậc đầu tiên, và từ bất kỳ bậc nào bạn cũng luôn có thể bước lên bậc kế tiếp, thì bạn có thể lên tới mọi bậc, dù cao đến đâu. Bạn không bao giờ cần kiểm tra vô hạn bậc thang từng cái một — chỉ cần kiểm tra bước đầu tiên và cơ chế 'bước tiếp theo' là đủ để bao quát tất cả cùng lúc.

Phác thảo chứng minh

Nguyên lý này suy ra từ tính sắp thứ tự tốt của các số tự nhiên: mọi tập con khác rỗng của {n0,n0+1,… }\{n_0, n_0+1, \dots\} đều có phần tử nhỏ nhất. Giả sử phản chứng rằng tập SS các số nguyên n≥n0n \ge n_0 mà P(n)P(n) sai là khác rỗng; gọi mm là phần tử nhỏ nhất của nó. Vì P(n0)P(n_0) đúng nên m≠n0m \ne n_0, do đó m−1≥n0m - 1 \ge n_0 và m−1∉Sm-1 \notin S (vì mm là nhỏ nhất), tức P(m−1)P(m-1) đúng. Theo bước quy nạp, P(m)P(m) phải đúng, mâu thuẫn với m∈Sm \in S. Vậy SS rỗng và P(n)P(n) đúng với mọi n≥n0n \ge n_0. (Tương đương, quy nạp và tính sắp thứ tự tốt của N\mathbb{N} có thể thay thế cho nhau và đều suy ra từ các tiên đề Peano.)

Người phát biểu

nêu năm 1654Blaise Pascal

Chủ đề chứa định lý này

Quy nạp toán học

Chứng minh từng bước

Chưa có chứng minh từng bước cho định lý này.

Tài liệu tham khảo

  1. Kenneth H. Rosen (2012). Discrete Mathematics and Its Applications
  2. George Pólya (1954). Induction and Analogy in Mathematics