Phương pháp quy nạp toán học là gì?
Quy nạp toán học là cách chứng minh một mệnh đề P(n) đúng với mọi số tự nhiên n ≥ 1 — tức là đúng với vô hạn trường hợp — mà chỉ cần làm hai việc hữu hạn. Ví dụ quen thuộc: chứng minh 1 + 3 + 5 + … + (2n−1) = n² với mọi n. Không ai kiểm tra nổi từng giá trị của n, nhưng quy nạp cho ta một "cỗ máy" tự lan truyền tính đúng từ số này sang số kế tiếp, hệt như dãy domino đổ dây chuyền.
Ý tưởng trực quan: hai điều kiện của dãy domino
Mỗi quân domino mang số thứ tự n tượng trưng cho mệnh đề P(n); "quân số n đổ" nghĩa là "P(n) đúng". Muốn tất cả các quân đổ, bạn cần đủ hai điều kiện — thiếu một là thất bại:
- Bước cơ sở: phải có ai đó đẩy quân số 1. Nếu không, dù các quân xếp sát nhau đến đâu cũng chẳng quân nào đổ.
- Bước quy nạp: các quân phải xếp đủ gần để bất kỳ quân k nào đổ cũng va trúng quân k+1. Chỉ cần một khoảng trống quá rộng là chuỗi dừng ngay tại đó.
- Khi cả hai điều kiện thỏa mãn, quân 1 đổ kéo quân 2, quân 2 kéo quân 3… và toàn bộ dãy — dù dài vô hạn — đều đổ.
- Trong game, hãy kéo khoảng cách vượt 100% chiều cao hoặc rút một quân ở giữa để thấy chuỗi gãy đúng chỗ điều kiện bị vi phạm.
Vì sao hai bước là đủ để kết luận cho vô hạn n?
Giả sử P(1) đúng và P(k) ⇒ P(k+1) với mọi k ≥ 1. Lấy một số n bất kỳ, chẳng hạn n = 100. Ta có chuỗi suy luận: P(1) đúng ⇒ P(2) đúng ⇒ P(3) đúng ⇒ … ⇒ P(100) đúng. Mỗi mũi tên là một lần áp dụng bước quy nạp — một cú va domino. Vì n tùy ý nên P(n) đúng với mọi n.
Điểm tinh tế nhất nằm ở bước quy nạp: ta không được giả sử P đúng với mọi số, mà chỉ giả sử P(k) đúng cho một số k nào đó (gọi là giả thiết quy nạp) rồi chứng minh P(k+1). Trong hình ảnh domino: ta không cần biết quân k có thật sự đổ hay không, chỉ cần chắc rằng nếu nó đổ thì nó với tới quân k+1. Việc "khởi động" là nhiệm vụ riêng của bước cơ sở.
Với ví dụ 1 + 3 + 5 + … + (2n−1) = n²: bước cơ sở n = 1 cho 1 = 1². Bước quy nạp: giả sử tổng k số lẻ đầu bằng k², thì thêm số lẻ tiếp theo (2k+1) được k² + 2k + 1 = (k+1)² — đúng dạng công thức với n = k+1. Cỗ máy domino đã được lắp xong.
Câu hỏi thường gặp
Phương pháp quy nạp toán học gồm những bước nào? Hai bước: bước cơ sở kiểm tra P(1) đúng; bước quy nạp giả sử P(k) đúng rồi chứng minh P(k+1) đúng. Từ đó P(n) đúng với mọi n ≥ 1.
Vì sao thiếu một trong hai bước thì chứng minh sụp đổ? Như domino: không đẩy quân 1 thì không gì đổ; còn nếu tồn tại một k mà P(k) không kéo theo P(k+1) — một khe hở quá rộng — thì chuỗi dừng tại k và mọi mệnh đề phía sau chưa được chứng minh.
Nếu mệnh đề chỉ đúng từ n = 5 trở đi thì sao? Vẫn dùng quy nạp, chỉ cần dời điểm xuất phát: bước cơ sở kiểm tra P(5), bước quy nạp làm với k ≥ 5 — tương đương đẩy quân số 5 thay vì quân số 1.
Ứng dụng thực tế
Tư duy "cơ sở + lan truyền" của quy nạp xuất hiện ở nhiều nơi:
- 💻 Lập trình: chứng minh vòng lặp và hàm đệ quy chạy đúng (đúng ở bước đầu + giữ đúng sau mỗi bước lặp) chính là quy nạp trá hình.
- 💰 Lãi kép và dãy truy hồi: biết số dư năm đầu và quy tắc chuyển từ năm k sang năm k+1 là suy ra được công thức cho mọi năm.
- 🏗 Kiểm định chất lượng dây chuyền: nếu sản phẩm đầu đạt chuẩn và mỗi công đoạn giữ nguyên chuẩn, thì mọi sản phẩm ra lò đều đạt chuẩn.
- 🧮 Rất nhiều công thức lớp 11 — tổng cấp số cộng, cấp số nhân, bất đẳng thức Bernoulli — đều được chứng minh chặt chẽ bằng quy nạp.