Chứng minh quy nạp dùng để chứng minh một mệnh đề đúng với mọi số tự nhiên n từ một mốc nào đó: chứng minh nó đúng ở mốc đầu tiên, rồi chứng minh hễ đúng ở một số k thì đúng ở k + 1. Hai mảnh đó ghép lại cho kết luận với mọi n, giống như hàng domino: quân đầu đổ, và quân nào đổ cũng làm quân sau đổ, thì cả hàng đổ.
Ý tưởng thì dễ, nhưng bài làm quy nạp của sinh viên năm nhất hay mất điểm vì cách viết: quên bước cơ sở, nhầm giả thiết quy nạp với điều cần chứng minh, hoặc bước quy nạp có một lỗ hổng chỉ lộ ra ở giá trị nhỏ. Bài này tập trung vào chuyện viết cho đúng và nhận ra chứng minh sai, phần nguyên lý quy nạp trong toán rời rạc có bài riêng ở danh mục đó.
Khung bốn phần của một chứng minh quy nạp
Một chứng minh quy nạp đầy đủ luôn có bốn phần. Viết rõ từng phần, kể cả khi phần nào đó có vẻ hiển nhiên, vì người chấm sẽ tìm đúng bốn phần này:
- Phát biểu mệnh đề P(n) và mốc bắt đầu. Ghi rõ P(n) là gì, và cần chứng minh nó với mọi n từ bao nhiêu trở đi. Nhiều lỗi bắt nguồn từ việc P(n) không được viết ra mà chỉ nằm trong đầu.
- Bước cơ sở. Kiểm trực tiếp P tại mốc đầu tiên, thường là n = 0 hoặc n = 1, nhưng có bài mốc là 4 hay 5. Đây là phép tính cụ thể, không phải lập luận chung.
- Bước quy nạp. Lấy một số k bất kỳ không nhỏ hơn mốc, giả sử P(k) đúng (gọi là giả thiết quy nạp), và chứng minh P(k + 1) đúng. Phải chỉ rõ chỗ nào dùng giả thiết quy nạp.
- Kết luận. Theo nguyên lý quy nạp, P(n) đúng với mọi n từ mốc trở đi. Một câu là đủ, nhưng không được bỏ.
Điểm tinh tế nằm ở bước ba. Bạn không giả sử "P(n) đúng với mọi n", vì đó chính là điều cần chứng minh. Bạn chỉ giả sử P đúng tại một số k cụ thể nhưng tuỳ ý, và chứng minh rằng tính đúng truyền được sang k + 1. Viết "giả sử P(k) đúng với một số k ≥ 1 nào đó" thay vì "giả sử P(k) đúng với mọi k" giúp tránh nhầm lẫn này.
Ví dụ một: tổng n số lẻ đầu tiên bằng n²
Mệnh đề P(n): 1 + 3 + 5 + … + (2n − 1) = n², với mọi n ≥ 1. Trước khi chứng minh, nên thử để tin: với n = 1 tổng là 1; n = 2 là 4; n = 3 là 9; n = 4 là 16. Đúng là các số chính phương liên tiếp.
Bước cơ sở: với n = 1, vế trái chỉ có một số hạng là 1, vế phải là 1² = 1. Hai vế bằng nhau, P(1) đúng.
Bước quy nạp: giả sử P(k) đúng với một số k ≥ 1 nào đó, tức 1 + 3 + … + (2k − 1) = k². Cần chứng minh P(k + 1): 1 + 3 + … + (2k − 1) + (2k + 1) = (k + 1)². Số hạng cuối của tổng mới là 2(k + 1) − 1 = 2k + 1. Theo giả thiết quy nạp, phần tổng tới 2k − 1 bằng k², nên vế trái bằng k² + 2k + 1 = (k + 1)². Vậy P(k + 1) đúng.
Kết luận: theo nguyên lý quy nạp, mệnh đề đúng với mọi n ≥ 1. Để ý câu "theo giả thiết quy nạp" ở giữa: đó là chỗ người chấm tìm đầu tiên. Một bước quy nạp không dùng tới giả thiết quy nạp ở đâu cả thường là dấu hiệu bạn đã chứng minh thứ khác, hoặc bài này không cần quy nạp.
Ví dụ hai: bất đẳng thức và vì sao mốc bắt đầu quan trọng
Mệnh đề: 2ⁿ > n² với mọi n ≥ 5. Thử các giá trị nhỏ cho thấy vì sao mốc là 5: với n = 2 thì 4 bằng 4, n = 3 thì 8 nhỏ hơn 9, n = 4 thì 16 bằng 16, còn n = 5 thì 32 lớn hơn 25. Với n = 1 thì 2 lớn hơn 1, đúng, nhưng các giá trị 2, 3, 4 làm mệnh đề sai nên không thể bắt đầu từ 1.
Bước cơ sở: n = 5, có 2⁵ = 32 > 25 = 5². Bước quy nạp: giả sử 2ᵏ > k² với một số k ≥ 5 nào đó. Khi đó 2ᵏ⁺¹ = 2·2ᵏ > 2k² theo giả thiết quy nạp. Còn phải chỉ ra 2k² ≥ (k + 1)². Khai triển, điều này tương đương k² − 2k − 1 ≥ 0, tức (k − 1)² ≥ 2, đúng khi k ≥ 3, và càng đúng khi k ≥ 5. Ghép lại: 2ᵏ⁺¹ > 2k² ≥ (k + 1)², nên P(k + 1) đúng.
Ví dụ này dạy hai điều. Thứ nhất, với bất đẳng thức, bước quy nạp thường gồm hai mảnh: một mảnh dùng giả thiết quy nạp, một mảnh là bất đẳng thức phụ cần chứng minh riêng, và bất đẳng thức phụ đó thường chỉ đúng từ một ngưỡng nào đó. Thứ hai, ngưỡng của bất đẳng thức phụ (ở đây là k ≥ 3) không nhất thiết trùng với mốc của bài (ở đây là 5). Mốc của bài do bước cơ sở quyết định; bạn phải kiểm cả hai.
Quy nạp mạnh: khi bước k + 1 cần nhiều hơn một bước trước
Quy nạp mạnh khác ở giả thiết. Thay vì chỉ giả sử P(k) đúng, bạn giả sử P đúng với mọi giá trị từ mốc đến k, rồi chứng minh P(k + 1). Về logic, hai dạng quy nạp có sức mạnh như nhau; quy nạp mạnh chỉ tiện hơn khi k + 1 phụ thuộc vào một giá trị nhỏ hơn bất kỳ, không chỉ k.
Ví dụ kinh điển: mọi số nguyên lớn hơn 1 là tích các số nguyên tố. Giả sử mọi số từ 2 đến k đều là tích các số nguyên tố. Xét k + 1. Nếu nó nguyên tố thì xong, vì một số nguyên tố là tích của một thừa số. Nếu không, k + 1 = a·b với a, b nằm giữa 2 và k. Theo giả thiết quy nạp mạnh, cả a và b là tích các số nguyên tố, nên tích của chúng cũng vậy.
Vì sao quy nạp thường không đủ ở ví dụ trên. Biết k là tích các số nguyên tố không cho bạn thông tin gì về k + 1, vì hai số liên tiếp không có ước chung lớn hơn 1. Thứ bạn cần là thông tin về a và b, những số nhỏ hơn hẳn k.
Có bao nhiêu bước cơ sở. Khi bước quy nạp dùng tới hai giá trị trước, như dãy mà số hạng sau bằng tổng hai số hạng trước, bạn cần kiểm hai giá trị đầu ở bước cơ sở. Quy tắc chung: số giá trị cơ sở phải đủ để bước quy nạp đầu tiên có đủ dữ liệu.
Chứng minh sai nổi tiếng: mọi con ngựa cùng màu
Đây là ví dụ được dùng rộng rãi để luyện mắt tìm lỗi. Mệnh đề giả: trong mọi đàn ngựa gồm n con, tất cả cùng màu. Bước cơ sở: đàn một con thì hiển nhiên cùng màu. Bước quy nạp: giả sử mọi đàn k con đều cùng màu. Lấy một đàn k + 1 con, xếp hàng. Bỏ con cuối, còn k con, theo giả thiết cùng màu. Bỏ con đầu, còn k con khác, cũng cùng màu. Hai nhóm này có chung những con ở giữa, nên cả đàn cùng một màu.
Lỗi nằm ở câu "hai nhóm có chung những con ở giữa". Khi k + 1 = 2, nhóm thứ nhất là con đầu, nhóm thứ hai là con cuối, và chúng không có con nào chung. Mỗi nhóm cùng màu với chính nó, nhưng không có gì nối hai nhóm với nhau. Vậy bước quy nạp đúng với k ≥ 2 nhưng hỏng đúng ở bước từ 1 sang 2, và một bước hỏng là đủ làm đứt cả hàng domino.
Bài học áp dụng được cho mọi chứng minh quy nạp: sau khi viết xong bước quy nạp tổng quát, hãy thử đưa giá trị k nhỏ nhất vào và kiểm từng câu xem có còn đúng không. Lỗi kiểu này không nằm trong đại số mà nằm trong một câu chữ tưởng như vô hại, và chỉ lộ ra khi bạn chạy lập luận trên giá trị cụ thể. Đây cũng là bài thử tốt cho chatbot: đưa nó chứng minh trên mà không nói là sai, xem nó có chỉ ra đúng bước từ 1 sang 2 không.
Dùng AI để luyện quy nạp đúng cách
Chatbot viết chứng minh quy nạp cho các tổng quen thuộc rất nhanh, nên chỗ đáng dùng nó là ở khâu kiểm và ra đề. Vài cách dùng có ích:
- Gửi chứng minh của bạn kèm câu lệnh: "Chỉ ra bốn phần của chứng minh quy nạp này, đánh dấu chỗ dùng giả thiết quy nạp. Nếu thiếu phần nào hoặc giả thiết quy nạp bị phát biểu sai, nói rõ nhưng đừng viết lại."
- Nhờ ra đề có bẫy: "Cho mình bốn mệnh đề cần chứng minh bằng quy nạp, trong đó một mệnh đề có mốc bắt đầu không phải 1 và một mệnh đề sai ở một giá trị nhỏ. Chỉ ghi đề."
- Nhờ tạo chứng minh sai để luyện mắt: "Viết một chứng minh quy nạp có một lỗi tinh vi, theo kiểu ví dụ những con ngựa cùng màu, về một chủ đề khác. Đừng nói lỗi ở đâu."
- Với mọi đẳng thức AI đưa ra, tự kiểm bằng hai ba giá trị n cụ thể. Một đẳng thức sai sẽ lộ ngay ở n = 2 hoặc 3, và AI đôi khi viết sai số hạng tổng quát.
- Không dùng AI để viết bài nộp được chấm điểm. Ở phần lớn các trường, đó là vi phạm quy định học thuật.
Một mẹo nhỏ khi đọc chứng minh do AI viết: tìm câu "theo giả thiết quy nạp". Nếu không có, hoặc có nhưng phép biến đổi ngay sau không thật sự dùng tới nó, bạn đang nhìn một chứng minh lỏng.
Câu hỏi thường gặp
Bước cơ sở trong quy nạp có thật sự cần thiết không?
Cần. Thiếu bước cơ sở, bước quy nạp có thể đúng mà mệnh đề vẫn sai ở mọi n. Ví dụ mệnh đề n bằng n cộng 1 có bước quy nạp đúng về mặt hình thức nhưng không có giá trị nào làm nó đúng.
Giả thiết quy nạp có phải là giả sử điều cần chứng minh không?
Không. Giả thiết quy nạp chỉ giả sử mệnh đề đúng tại một số k cụ thể nhưng tuỳ ý, rồi chứng minh nó đúng tại k cộng 1. Giả sử đúng với mọi n mới là lập luận vòng.
Khi nào nên dùng quy nạp mạnh thay vì quy nạp thường?
Khi để chứng minh mệnh đề tại k cộng 1, bạn cần biết nó đúng ở một giá trị nhỏ hơn bất kỳ chứ không chỉ ở k. Ví dụ phân tích thành tích số nguyên tố hay các dãy mà số hạng sau phụ thuộc nhiều số hạng trước.
Mốc bắt đầu của quy nạp có nhất thiết là 1 không?
Không. Mốc là giá trị nhỏ nhất mà bạn muốn mệnh đề đúng, có thể là 0, 1, 5 hay số khác. Ví dụ 2 mũ n lớn hơn n bình phương chỉ đúng từ n bằng 5, nên bước cơ sở phải kiểm tại 5.
Làm sao phát hiện lỗi trong một chứng minh quy nạp trông có vẻ đúng?
Đưa giá trị k nhỏ nhất vào bước quy nạp và đọc lại từng câu xem còn đúng không. Lỗi kiểu những con ngựa cùng màu chỉ lộ ra khi chạy lập luận trên giá trị cụ thể nhỏ.
Chatbot có viết đúng chứng minh quy nạp không?
Với các tổng quen thuộc thì thường đúng, nhưng đôi khi viết sai số hạng tổng quát, bỏ bước cơ sở hoặc không dùng thật sự giả thiết quy nạp. Luôn kiểm bằng giá trị cụ thể và tìm chỗ dùng giả thiết quy nạp.