Quy nạp toán học là cách chứng minh một điều đúng cho mọi số tự nhiên chỉ bằng hai bước: chỉ ra nó đúng với số đầu tiên, và chỉ ra rằng hễ nó đúng với một số nào đó thì nó cũng đúng với số liền sau. Hai bước ấy giống như đẩy quân domino đầu tiên và chắc chắn mỗi quân đều đủ gần để kéo quân sau ngã theo.
Chào bạn, đây là Nhà Toán Học. Học sinh lớp mười một gặp quy nạp và thường thấy nó như một nghi thức viết cho đủ bước. Tập này mình muốn bạn thấy vì sao hai bước đó là đủ, và vì sao thiếu một trong hai là sụp cả.
Vì sao chỉ hai bước mà phủ được vô số trường hợp?
Bạn thử hình dung một hàng domino kéo dài vô tận. Muốn chắc cả hàng đều ngã, bạn không cần nhìn từng quân. Bạn chỉ cần hai điều: quân đầu tiên bị đẩy, và quân nào ngã cũng đổ được vào quân kế tiếp.
Có hai điều đó, quân thứ nhất ngã kéo quân thứ hai, quân thứ hai kéo quân thứ ba, cứ thế mãi. Không có quân nào đứng sót được, vì muốn nó đứng thì quân ngay trước nó phải đứng, và cứ lùi về như vậy tới tận quân đầu tiên, mà quân đầu đã ngã.
Trong toán, bước đẩy quân đầu gọi là bước cơ sở, còn bước quân nào cũng kéo quân sau gọi là bước quy nạp. Bước quy nạp không chứng minh mệnh đề đúng ở số nào cả. Nó chỉ chứng minh một mối nối: nếu đúng ở đây thì đúng ở kế tiếp.
Nhiều bạn thấy bước quy nạp như ăn gian, vì giả sử nó đúng rồi lại dùng nó. Thật ra mình không giả sử điều cần chứng minh, mình chỉ giả sử cho một số cụ thể để xét số liền sau. Đó là xét một mối nối, không phải vòng luẩn quẩn.
Ví dụ đẹp: cộng các số lẻ liên tiếp luôn ra số chính phương
Một cộng ba bằng bốn. Một cộng ba cộng năm bằng chín. Thêm bảy được mười sáu. Thêm chín được hai mươi lăm. Bốn, chín, mười sáu, hai mươi lăm đều là bình phương của một số. Có vẻ tổng của mấy số lẻ đầu tiên thì bằng bình phương của chính số lượng ấy.
Bước cơ sở: một số lẻ đầu tiên là một, bằng một bình phương. Đúng. Bước quy nạp: giả sử tổng của một số lượng số lẻ đầu tiên bằng bình phương của số lượng đó, gọi số lượng là ka. Thêm số lẻ kế tiếp, tức là hai ka cộng một, thì tổng mới là ka bình phương cộng hai ka cộng một, đúng bằng ka cộng một, tất cả bình phương.
Thế là xong, cả hàng domino đổ. Có một cách nhìn bằng hình rất dễ nhớ. Xếp các hạt đậu thành hình vuông, mỗi lần mở rộng hình vuông thêm một hàng và một cột, mình cần thêm đúng một số lẻ hạt đậu, gấp khúc như chữ L.
Hình vẽ giúp mình tin, còn quy nạp giúp mình viết ra cho chặt để người khác kiểm.
Mọi con ngựa cùng màu: một chứng minh sai rất khéo
Có một lập luận nổi tiếng chứng minh mọi con ngựa trên đời cùng một màu. Bước cơ sở: một nhóm chỉ có một con ngựa thì hiển nhiên cùng màu. Bước quy nạp: giả sử nhóm nào có ka con cũng cùng màu, xét một nhóm ka cộng một con.
Bỏ con đầu tiên ra, còn ka con, cùng màu. Bỏ con cuối cùng ra, còn ka con khác, cũng cùng màu. Hai nhóm này chồng lên nhau ở những con giữa, nên cả đàn cùng màu. Nghe trơn tru, vậy sai ở đâu.
Sai ở đúng một mối nối: từ một con lên hai con. Khi đàn có hai con, bỏ con đầu còn con thứ hai, bỏ con cuối còn con thứ nhất. Hai nhóm này không có con nào chung, nên không thể nói chúng cùng màu với nhau. Quân domino thứ nhất không chạm được quân thứ hai.
Bài học là bước quy nạp phải đúng với mọi ka, kể cả ka nhỏ nhất. Một mối nối đứt là cả hàng dừng lại. Khi tự kiểm chứng minh quy nạp, hãy thử bước quy nạp với số nhỏ nhất xem lý lẽ còn đứng không.
Những lỗi học sinh hay mắc khi viết quy nạp
Lỗi thứ nhất là quên bước cơ sở vì thấy nó hiển nhiên. Có những mệnh đề mà bước quy nạp đúng nhưng bước cơ sở sai, và khi đó cả mệnh đề sai. Ví dụ mệnh đề mọi số tự nhiên đều bằng chính nó cộng một có bước quy nạp chạy được, nhưng không có quân đầu nào ngã.
Lỗi thứ hai là chứng minh bước quy nạp bằng cách thử vài số. Thử ka bằng hai, ka bằng ba thấy đúng rồi kết luận, như vậy là quay về kiểu thấy đúng nhiều lần, không phải quy nạp.
Lỗi thứ ba là dùng điều cần chứng minh cho số ka cộng một ngay trong lúc chứng minh nó. Bạn chỉ được dùng giả thiết cho số ka, rồi biến đổi cho tới khi ra kết luận cho số ka cộng một.
Mẹo nhỏ của các thầy dạy đội tuyển: trước khi viết, hãy tự viết ra câu cần chứng minh ở bước ka cộng một, rồi nhìn xem nó khác câu ở bước ka chỗ nào. Chỗ khác đó chính là phần mình phải xử lý.
Quy nạp ngoài sách giáo khoa
Quy nạp không chỉ để chứng minh công thức tổng. Nó là cách nghĩ khi gặp một bài lớn: nếu giải được bài cỡ nhỏ hơn một chút, mình có dùng được nó để giải bài cỡ hiện tại không.
Một ví dụ dễ chơi là bài chia kẹo. Có một nhóm bạn, mỗi người nắm một số kẹo, mỗi lượt một người đưa một viên cho người khác. Muốn chứng minh một điều đúng sau bất kỳ số lượt nào, mình xem nó đúng lúc đầu, và mỗi lượt có giữ nó đúng không.
Cách nghĩ này cũng giúp ngoài đời. Muốn giữ một thói quen lâu dài, mình không cần nghĩ tới một năm. Chỉ cần chắc ngày hôm nay làm được, và ngày nào làm được thì ngày mai cũng dễ làm hơn.
Câu đố nhỏ: dùng quy nạp, bạn thử chứng minh rằng một bàn cờ có cạnh là hai mũ ka, bị khoét đi một ô bất kỳ, luôn lát kín được bằng các miếng hình chữ L gồm ba ô.
Câu hỏi thường gặp
Quy nạp toán học có phải là suy luận quy nạp trong triết học không?
Không. Suy luận quy nạp trong đời thường là đi từ nhiều quan sát tới một kết luận chung, kết luận đó có thể sai. Quy nạp toán học là một phép suy diễn chặt chẽ, nếu làm đủ hai bước thì kết luận chắc chắn đúng.
Bước cơ sở có bắt buộc bắt đầu từ số một không?
Không. Bước cơ sở bắt đầu từ số đầu tiên mà mệnh đề nói tới. Có mệnh đề chỉ đúng từ số năm trở đi, khi đó bước cơ sở là số năm và kết luận cũng chỉ áp dụng từ số năm.
Quy nạp mạnh là gì?
Quy nạp mạnh cho phép giả sử mệnh đề đúng với tất cả các số từ số đầu tiên tới số ka, chứ không chỉ riêng số ka, rồi suy ra đúng với số ka cộng một. Nó tiện khi số kế tiếp phụ thuộc vào nhiều số trước đó, như trong dãy Fibonacci.
Vì sao sách hay chọn ví dụ tổng để dạy quy nạp?
Vì công thức tổng có cấu trúc rất rõ: tổng mới bằng tổng cũ cộng thêm một số hạng. Cấu trúc đó khớp hoàn hảo với bước quy nạp, nên người mới học dễ thấy mối nối.
Có cách nào kiểm nhanh một chứng minh quy nạp mình vừa viết?
Hãy đọc lại bước quy nạp với giá trị nhỏ nhất của ka và hỏi lý lẽ có còn đứng không. Rồi kiểm xem mình đã dùng giả thiết quy nạp ở đúng chỗ chưa. Một chứng minh quy nạp mà không dùng tới giả thiết thường là dấu hiệu có gì đó lạ.
