Lớp 11

Quy nạp toán học

Chứng minh mệnh đề với mọi số tự nhiên qua bước cơ sở và bước quy nạp, quy nạp mạnh, nguyên lý sắp thứ tự tốt và giới hạn của quy nạp.

Hãy tưởng tượng một hàng quân domino dài vô hạn dựng thẳng đứng. Làm sao chắc chắn mọi quân đều đổ? Chỉ cần hai điều: (1) ta đẩy đổ quân đầu tiên, và (2) hễ một quân nào đổ thì nó đứng đủ gần để làm đổ quân tiếp theo. Quy nạp toán học chính là dây chuyền domino này được biến thành phương pháp chứng minh chặt chẽ cho các mệnh đề với mọi số tự nhiên $n = 1, 2, 3, \dots$ .

Phổ thôngNguyên lý quy nạp toán học

Định lý: Nguyên lý quy nạp toán học

Cho $P(n)$ là một mệnh đề phụ thuộc vào số nguyên dương $n$ . Nếu (1) bước cơ sở: $P(1)$ đúng, và (2) bước quy nạp: với mọi số nguyên $k \ge 1$ , giả sử $P(k)$ đúng (giả thiết quy nạp) kéo theo $P(k+1)$ cũng đúng, thì $P(n)$ đúng với mọi số nguyên $n \ge 1$ .

Vì sao đúng?

Từ $P(1)$ và kéo theo $P(1) \Rightarrow P(2)$ ta có $P(2)$ ; từ $P(2)$ và $P(2) \Rightarrow P(3)$ ta có $P(3)$ ; cứ thế mãi, chạm tới bất kỳ số nguyên $n$ nào sau hữu hạn bước. Trong số học tiên đề (hệ tiên đề Peano), quy nạp là một trong các tiên đề định nghĩa tập số tự nhiên.

Chứng minh

Giả sử $P(1)$ đúng và với mọi số nguyên $k \ge 1$ , mệnh đề kéo theo $P(k) \Rightarrow P(k+1)$ đúng. Để chứng minh $P(n)$ đúng với mọi $n \ge 1$ , giả sử phản chứng rằng tập hợp các phản ví dụ $S = \{n \in \mathbb{Z}_{\ge 1} : P(n) \text{ is false}\}$ khác rỗng.

Theo nguyên lý sắp thứ tự tốt của tập số nguyên dương $\mathbb{Z}_{\ge 1}$ , tập con khác rỗng $S$ có một phần tử nhỏ nhất $m = \min S \ge 1$ . Vì $P(1)$ đúng theo giả thiết bước cơ sở nên $1 \notin S$ , suy ra $m \ge 2$ và do đó $m - 1 \ge 1$ .

Vì $m - 1 < m$ và $m$ là phần tử nhỏ nhất của $S$ , ta phải có $m - 1 \notin S$ , nghĩa là $P(m-1)$ đúng. Áp dụng bước quy nạp với $k = m - 1 \ge 1$ ta được $P(m-1) \Rightarrow P(m)$ , nên $P(m)$ đúng. Điều này mâu thuẫn với $m \in S$ , chứng tỏ $S = \varnothing$ và vì vậy $P(n)$ đúng với mọi $n \ge 1$ .

\bigl(P(1) \;\wedge\; \forall k \ge 1,\; (P(k) \Rightarrow P(k+1))\bigr) \;\Longrightarrow\; \forall n \ge 1,\; P(n)

Ví dụ: Tổng n số nguyên dương đầu tiên

Chứng minh rằng với mọi số nguyên $n \ge 1$ , $1 + 2 + \cdots + n = \frac{n(n+1)}{2}$ .

Lời giải

**Bước cơ sở ( $n = 1$ ):** Vế trái bằng $1$ , vế phải bằng $\frac{1(1+1)}{2} = 1$ , vậy $P(1)$ đúng.

Bước quy nạp: Giả sử $P(k)$ đúng với một $k \ge 1$ nào đó, tức là $1 + 2 + \cdots + k = \frac{k(k+1)}{2}$ . Cộng $k + 1$ vào hai vế, ta được $1 + 2 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1) = (k+1)\left(\frac{k}{2} + 1\right) = \frac{(k+1)(k+2)}{2}$ , chính là $P(k+1)$ . Theo nguyên lý quy nạp toán học, công thức đúng với mọi $n \ge 1$ .

\sum_{j=1}^{n} j^2 = 1^2 + 2^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6} = \frac{1}{3}n^3 + \frac{1}{2}n^2 + \frac{1}{6}n

Trực quan hóa tổng rời rạc và diện tích liên tục: điều chỉnh số hình chữ nhật

n

để so sánh tổng bậc thang

\sum_{j=1}^{n} j^2 = \frac{n(n+1)(2n+1)}{6}

với tích phân

\int_0^n x^2\,dx = \frac{n^3}{3}

, minh họa cách mỗi bước quy nạp cộng thêm cột diện tích tiếp theo

(k+1)^2

Ví dụ: Một bất đẳng thức mũ

Chứng minh rằng $2^n > n$ với mọi số nguyên $n \ge 1$ .

Lời giải

**Bước cơ sở ( $n = 1$ ):** $2^1 = 2 > 1$ , đúng.

Bước quy nạp: Giả sử $2^k > k$ với một $k \ge 1$ nào đó. Nhân hai vế với $2$ , ta được $2^{k+1} = 2 \cdot 2^k > 2k = k + k \ge k + 1$ (vì $k \ge 1$ ). Do đó $2^{k+1} > k + 1$ , hoàn tất phép quy nạp.

Đại họcQuy nạp mạnh và nguyên lý sắp thứ tự tốt

Định nghĩa: Quy nạp mạnh (quy nạp đầy đủ)

Để chứng minh $P(n)$ với mọi $n \ge n_0$ , chỉ cần kiểm tra $P(n_0)$ và chứng minh rằng với mọi $k \ge n_0$ , nếu tất cả $P(n_0), P(n_0+1), \dots, P(k)$ đều đúng thì $P(k+1)$ đúng. Dù mang tên quy nạp mạnh, nó tương đương logic với quy nạp thường: chỉ cần áp dụng quy nạp thường cho mệnh đề gộp $Q(n) = P(n_0) \wedge P(n_0+1) \wedge \cdots \wedge P(n)$ .

Định lý: Nguyên lý quy nạp mạnh và sự tương đương logic

Cho $P(n)$ là mệnh đề với các số nguyên $n \ge n_0$ . Nếu $P(n_0)$ đúng và với mọi số nguyên $k \ge n_0$ , giả thiết kéo theo $\bigl(P(n_0) \wedge \cdots \wedge P(k)\bigr) \Rightarrow P(k+1)$ đúng, thì $P(n)$ đúng với mọi số nguyên $n \ge n_0$ . Hơn nữa, quy nạp mạnh, quy nạp thường và nguyên lý sắp thứ tự tốt tương đương logic với nhau.

Vì sao đúng?

Quy nạp mạnh cho phép ta sử dụng bất kỳ trường hợp trước đó $P(j)$ nào với $n_0 \le j \le k$ (chẳng hạn $a, b \le k$ khi phân tích $k+1 = a b$ hoặc $P(k-1)$ và $P(k)$ trong hệ thức truy hồi Fibonacci) mà không cần thêm tiên đề nào ngoài quy nạp thường.

Chứng minh

Đưa về quy nạp thường: Cho vị từ $P(n)$ với $n \ge n_0$ , định nghĩa mệnh đề hội tích lũy $Q(n) \equiv P(n_0) \wedge P(n_0+1) \wedge \cdots \wedge P(n)$ . Tại chỉ số cơ sở $n = n_0$ , mệnh đề $Q(n_0)$ chỉ có một hạng tử $P(n_0)$ , đúng theo giả thiết cơ sở của quy nạp mạnh.

**Bước quy nạp cho $Q(k)$ :** Cố định số nguyên $k \ge n_0$ và giả sử $Q(k)$ đúng. Theo định nghĩa của $Q(k)$ , tất cả các mệnh đề $P(n_0), P(n_0+1), \dots, P(k)$ đều đúng. Giả thiết bước quy nạp mạnh $\bigl(P(n_0) \wedge \cdots \wedge P(k)\bigr) \Rightarrow P(k+1)$ khi đó suy ra $P(k+1)$ cũng đúng.

Kết luận: Kết hợp $Q(k)$ với $P(k+1)$ ta chứng minh được $Q(k+1) \equiv Q(k) \wedge P(k+1)$ . Áp dụng nguyên lý quy nạp toán học thông thường cho $Q(n)$ , mệnh đề $Q(n)$ đúng với mọi số nguyên $n \ge n_0$ ; nói riêng, hạng tử cuối $P(n)$ đúng với mọi $n \ge n_0$ .

Ví dụ: Sự tồn tại phân tích thừa số nguyên tố

Chứng minh rằng mọi số nguyên $n \ge 2$ hoặc là số nguyên tố, hoặc là tích của các số nguyên tố.

Lời giải

**Bước cơ sở ( $n = 2$ ):** $2$ là số nguyên tố.

Bước quy nạp mạnh: Cố định $k \ge 2$ và giả sử mọi số nguyên $m$ với $2 \le m \le k$ đều là số nguyên tố hoặc tích các số nguyên tố. Xét $k + 1$ . Nếu $k + 1$ nguyên tố thì xong. Ngược lại, $k + 1 = a b$ với các số nguyên $a, b$ thỏa $2 \le a, b \le k$ . Quy nạp thường không giúp được vì $a$ và $b$ không bằng $k$ , chỉ $\le k$ . Theo giả thiết quy nạp mạnh, cả $a$ và $b$ đều là tích các số nguyên tố, nên tích của chúng $k + 1 = a b$ cũng là tích các số nguyên tố.

Định nghĩa: Nguyên lý sắp thứ tự tốt

Mọi tập con khác rỗng $S \subseteq \mathbb{N}$ của các số nguyên dương đều có một phần tử nhỏ nhất $m \in S$ sao cho $m \le x$ với mọi $x \in S$ .

Nguyên lý sắp thứ tự tốt, quy nạp thường và quy nạp mạnh là ba diện mạo của cùng một nguyên lý. Để suy ra quy nạp từ sắp thứ tự tốt, giả sử $P(1)$ đúng và $P(k) \Rightarrow P(k+1)$ với mọi $k \ge 1$ , nhưng $P(n)$ vẫn sai với một $n$ nào đó. Khi đó tập các phản ví dụ $S = \{n \ge 1 : P(n) \text{ is false}\}$ khác rỗng, nên theo nguyên lý sắp thứ tự tốt nó có phần tử nhỏ nhất $m$ . Không thể có $m = 1$ vì $P(1)$ đúng; do đó $m - 1 \ge 1$ không thuộc $S$ , nghĩa là $P(m-1)$ đúng. Theo bước quy nạp, $P(m)$ cũng phải đúng, mâu thuẫn với $m \in S$ . Cách trình bày này thường gọi là phương pháp phản ví dụ nhỏ nhất.

Nâng caoQuy nạp hình học: Lát bảng bằng quân tromino

Ví dụ: Bài toán lát tromino của Golomb (1954)

Một quân L-tromino là mảnh ghép gồm $3$ ô vuông đơn vị xếp hình chữ L. Chứng minh rằng với mọi số nguyên $n \ge 1$ , bất kỳ bàn cờ $2^n \times 2^n$ nào bị khuyết một ô tùy ý đều lát kín được bằng các quân L-tromino không chồng lên nhau.

Lời giải

Lưu ý rằng việc phát biểu mạnh hơn cho bất kỳ ô khuyết nào (chứ không riêng ô ở góc) chính là chìa khóa để quy nạp chạy được. **Bước cơ sở ( $n = 1$ ):** Bỏ một ô bất kỳ khỏi bàn $2 \times 2$ sẽ còn lại hình chữ L gồm $3$ ô, đặt vừa khít $1$ quân tromino.

Bước quy nạp: Giả sử mệnh đề đúng cho bàn $2^k \times 2^k$ . Chia bàn $2^{k+1} \times 2^{k+1}$ (đã khuyết một ô) thành bốn góc phần tư kích thước $2^k \times 2^k$ . Ô khuyết nằm ở một góc phần tư. Đặt một quân L-tromino ngay tâm bàn cờ sao cho $3$ ô của nó che mỗi góc phần tư còn lại đúng một ô ở góc tâm. Khi đó cả bốn bàn con $2^k \times 2^k$ đều khuyết đúng một ô, nên theo giả thiết quy nạp cả bốn đều lát kín được.

Nghiên cứuNhững cạm bẫy tinh vi và giới hạn của quy nạp

Lỗi hay gặp. Ngụy biện Pólya: "Mọi con ngựa đều cùng màu." Đặt

P(n)

là: trong mọi tập gồm

n

con ngựa, tất cả đều có cùng một màu. **Bước cơ sở (

n = 1

): Một con ngựa hiển nhiên cùng màu với chính nó. "Bước quy nạp":** Cho

k + 1

con ngựa

\{h_1, h_2, \dots, h_{k+1}\}

k

con đầu

\{h_1, \dots, h_k\}

cùng màu theo

P(k)

, và

k

con cuối

\{h_2, \dots, h_{k+1}\}

cũng cùng màu theo

P(k)

; vì các con ở giữa

\{h_2, \dots, h_k\}

thuộc cả hai nhóm nên cả

k + 1

con phải cùng màu! Lỗi ở đâu? Kéo theo

P(k) \Rightarrow P(k+1)

bị gãy đúng tại

k = 1

: với

k + 1 = 2

con ngựa, hai tập con

\{h_1\}

và

\{h_2\}

có giao bằng rỗng

\{h_2, \dots, h_k\} = \varnothing

, nên không có con ngựa chung nào nối màu của hai nhóm.

Vì sao không phải mệnh đề đúng nào về số nguyên cũng chứng minh được ngay bằng quy nạp theo $n$ ? Một ví dụ điển hình là giả thuyết Collatz (`collatz-conjecture`, nêu năm 1937): xuất phát từ số nguyên dương $n$ bất kỳ, lặp lại quy tắc thay số chẵn $x$ bằng $x/2$ và thay số lẻ $x$ bằng $3x + 1$ ; giả thuyết khẳng định quỹ đạo luôn chạm tới $1$ . Nếu thử quy nạp mạnh theo $n$ , số chẵn $2k$ giảm ngay về $k < 2k$ nên dùng được giả thiết quy nạp—nhưng số lẻ $2k + 1$ lại nhảy vọt lên $6k + 4 > 2k + 1$ , vượt ra ngoài phạm vi mà giả thiết quy nạp $P(1), \dots, P(2k+1)$ bao phủ.

Hiện trạng nghiên cứu tính đến năm 2026

Tính đến năm 2026, giả thuyết Collatz (`collatz-conjecture`) vẫn là bài toán mở. Giai đoạn 2020–2021, David Bařina đã kiểm chứng bằng máy tính rằng mọi giá trị xuất phát $n < 2^{68}$ đều đi tới $1$ (và các đợt chạy tiếp theo đã vượt qua $2^{70}$ ), nhưng kiểm tra hàng tỷ tỷ trường hợp cơ sở mà không có bước quy nạp thì không bao giờ là chứng minh. Đột phá lý thuyết mạnh nhất là định lý năm 2019 của Terence Tao (công bố năm 2022), chứng minh rằng với hầu hết số nguyên dương $n$ (theo mật độ lôgarit), quỹ đạo Collatz đạt tới giá trị nhỏ cỡ $f(n)$ với mọi hàm $f(n) \to \infty$ . Việc nối khoảng cách từ "hầu hết" sang "mọi" $n$ —hoặc tìm được một đại lượng sắp thứ tự tốt giảm dần dọc theo quỹ đạo—vẫn nằm ngoài tầm với.

Trong chứng minh quy nạp toán học cho mệnh đề $P(n)$ với mọi $n \ge 1$ , bước quy nạp phải chứng minh điều gì?

Chứng minh quy nạp ngụy biện của Pólya rằng "mọi con ngựa đều cùng màu" bị gãy ở đâu?

Quy nạp mạnh khác quy nạp thường ở điểm nào?

Vì sao quy nạp mạnh ngây thơ theo $n$ không chứng minh được giả thuyết Collatz?

Tài liệu tham khảo

Florian Cajori (1918). Origin of the Name 'Mathematical Induction' · DOI:10.1080/00029890.1918.11998404
Solomon W. Golomb (1954). Checkerboards and Polyominoes · DOI:10.1080/00029890.1954.11988548
David Bařina (2021). Convergence verification of the Collatz problem · DOI:10.1007/s11227-020-03368-x