Quy nạp toán học — Nguyên lý, các bước & ví dụ

Quy nạp toán học là một phương pháp chứng minh dùng để chỉ ra rằng một mệnh đề đúng với mọi số nguyên kể từ một giá trị bắt đầu nào đó. Để chứng minh một khẳng định đúng với mọi $n \ge n_0$, bạn cần chỉ ra trường hợp đầu tiên là đúng, rồi chứng minh rằng nếu mệnh đề đúng tại một số nguyên thì nó cũng đúng tại số nguyên kế tiếp.

Nếu cả hai phần đều đúng, thì mệnh đề sẽ đúng với mọi số nguyên trong miền đã nêu. Đó chính là toàn bộ ý tưởng.

Quy nạp toán học hoạt động như thế nào

Viết mệnh đề dưới dạng $P(n)$. Khi đó, quy nạp có cấu trúc như sau:

1. Chứng minh bước cơ sở: chỉ ra rằng $P(n_0)$ là đúng.
2. Chứng minh bước quy nạp: chỉ ra rằng nếu $P(k)$ đúng với một số nguyên bất kỳ $k \ge n_0$, thì $P(k+1)$ cũng đúng.

Khi hoàn thành hai bước này, bạn có thể kết luận rằng $P(n)$ đúng với mọi số nguyên $n \ge n_0$.

Lập luận ở đây mang tính tuần tự. Bước cơ sở khởi đầu chuỗi, còn bước quy nạp giúp chuỗi tiếp tục tiến lên từng số nguyên một.

Vì sao cả bước cơ sở và bước quy nạp đều quan trọng

Bước cơ sở cho bạn mệnh đề đúng đầu tiên. Bước quy nạp nói rằng tính đúng đắn được truyền từ một số nguyên sang số nguyên kế tiếp.

Vì vậy, nếu $P(n_0)$ đúng thì $P(n_0 + 1)$ đúng. Khi đó $P(n_0 + 2)$ cũng đúng, và cứ tiếp tục như vậy. Quy nạp không được bỏ qua điểm bắt đầu, và cũng không được bỏ qua mắt xích nối từ trường hợp này sang trường hợp kế tiếp.

Ví dụ chi tiết: chứng minh công thức tổng bằng quy nạp

Một ví dụ quen thuộc là công thức

$$1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$$

đúng với mọi số nguyên $n \ge 1$.

Đặt

$$P(n): 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$$

Bước cơ sở

Lấy $n = 1$. Vế trái bằng $1$, còn vế phải là

$$\frac{1(1+1)}{2} = 1$$

Vậy $P(1)$ là đúng.

Bước quy nạp

Giả sử $P(k)$ đúng với một số nguyên bất kỳ $k \ge 1$. Điều đó có nghĩa là

$$1 + 2 + 3 + \cdots + k = \frac{k(k+1)}{2}$$

Bây giờ chứng minh $P(k+1)$. Bắt đầu từ vế trái ứng với $k+1$:

$$1 + 2 + 3 + \cdots + k + (k+1)$$

Dùng giả thiết quy nạp, ta được

$$\frac{k(k+1)}{2} + (k+1)$$

Đặt nhân tử chung $(k+1)$:

$$(k+1)\left(\frac{k}{2} + 1\right)$$

Sau đó rút gọn:

$$(k+1)\left(\frac{k+2}{2}\right) = \frac{(k+1)(k+2)}{2}$$

Đây chính là công thức khi $n = k+1$. Vậy $P(k+1)$ là đúng.

Vì cả bước cơ sở và bước quy nạp đều đã được chứng minh, công thức đúng với mọi số nguyên $n \ge 1$.

Khi nào nên dùng quy nạp toán học

Quy nạp hữu ích khi một mệnh đề phụ thuộc vào một tham số nguyên và mỗi trường hợp có liên hệ tự nhiên với một trường hợp trước đó. Điều này thường gặp trong các bài toán về tổng, tính chia hết, bất đẳng thức, hệ thức truy hồi và chứng minh thuật toán.

Trước hết, hãy xác định đúng giá trị bắt đầu. Có mệnh đề bắt đầu từ $n = 0$, có mệnh đề từ $n = 1$, và cũng có mệnh đề chỉ có ý nghĩa với các số nguyên lớn hơn.

Sau đó, kiểm tra xem trường hợp hợp lệ tiếp theo là gì. Bước thông thường là từ $k$ đến $k+1$, nhưng nếu mệnh đề chỉ nói về các số nguyên chẵn thì bước từ $k$ đến $k+2$ có thể mới là phiên bản phù hợp.

Những lỗi thường gặp trong chứng minh quy nạp

Chỉ chứng minh bước cơ sở

Bước cơ sở chỉ kiểm tra giá trị đầu tiên. Tự nó không đủ để chứng minh mệnh đề cho các số nguyên về sau.

Dùng sai giá trị bắt đầu

Nếu mệnh đề cần đúng với mọi $n \ge 2$, thì việc chỉ chứng minh $P(1)$ không giúp ích gì. Bước cơ sở phải khớp với đúng miền của mệnh đề.

Dùng giả thiết quy nạp một cách cẩu thả

Trong bước quy nạp, bạn giả sử $P(k)$ đúng với một số nguyên bất kỳ $k$ trong miền hợp lệ. Bạn không được giả sử rằng toàn bộ định lý đã được chứng minh xong.

Chứng minh sai trường hợp kế tiếp

Nếu định lý của bạn cần bước $k \to k+1$, thì việc chứng minh một bước khác sẽ không hoàn tất lập luận, trừ khi bạn giải thích vì sao bước khác đó là đủ.

Một mở rộng hữu ích: quy nạp mạnh

Đôi khi để chứng minh $P(k+1)$, chỉ biết $P(k)$ là chưa đủ. Trong tình huống đó, quy nạp mạnh cho phép bạn giả sử mọi trường hợp trước đó đến $k$ đều đúng, rồi chứng minh trường hợp tiếp theo.

Ý tưởng này có liên hệ rất gần với quy nạp thông thường, nhưng giả thiết mạnh hơn. Nó hữu ích, chẳng hạn khi một chứng minh phụ thuộc vào việc tách một số thành các phần nhỏ hơn.

Hãy tự thử một phiên bản khác

Xét mệnh đề

$$1 + 3 + 5 + \cdots + (2n - 1) = n^2$$

và chứng minh nó đúng với mọi số nguyên $n \ge 1$ bằng cùng cấu trúc: bước cơ sở trước, rồi bước từ $k$ đến $k+1$. Nếu bạn có thể viết chứng minh đó một cách gọn gàng, thì thường là bạn đã thật sự nắm được phương pháp này.