Chương 18: Quy nạp toán học

Câu hỏi mở đầu

Có một loại "với mọi" đặc biệt: với mọi số tự nhiên \(n\). Bổ đề 2 và bài C3 của Chương 17 đều ngầm dùng một tính chất riêng của các số tự nhiên: không thể giảm mãi. Liệu tính chất ấy có cho phép chứng minh một điều cho vô số trường hợp \(n = 0, 1, 2, \dots\) chỉ bằng hai bước hữu hạn?

Hàng domino

Dựng một hàng quân domino dài vô tận, các quân đủ gần nhau. Muốn chắc chắn mọi quân đều đổ, không cần theo dõi từng quân. Chỉ cần biết hai điều: quân đầu tiên đổ, và quân nào đổ cũng đẩy đổ quân kế tiếp nó. Từ hai điều ấy, quân thứ hai đổ, rồi quân thứ ba, rồi quân thứ một triệu: không quân nào đứng vững được.

Hai điều là đủ: quân đầu tiên đổ, và mỗi quân đổ đẩy đổ quân kế tiếp. Khi ấy mọi quân đều đổ.

Sách này đã dùng lối nghĩ ấy mà chưa gọi tên. Ở Chương 1, mỗi lớp chữ L biến một hình vuông \(k \times k\) thành hình vuông \((k + 1) \times (k + 1)\), nên tổng các số lẻ luôn là số chính phương. Ở Chương 12, luật \(a^m \cdot a^n = a^{m+n}\) được chứng minh cho \(n = 1\), rồi "đúng với \(n\) thì đúng với \(n + 1\)". Ở Chương 4, hai nhóm mất dần từng phần tử một. Chương này nói rõ lối lập luận ấy là gì, vì sao nó hợp lệ, và dùng nó thế nào.

Vì sao hai bước là đủ

Hàng domino chỉ là một hình ảnh; lý do thật nằm ở cấu trúc của các số tự nhiên. Chương 4 đã xây chúng bằng việc đếm: bắt đầu từ 0, mỗi lần thêm 1. Mọi số tự nhiên đều đạt được theo đúng cách ấy, sau hữu hạn bước. Không có số tự nhiên nào "lạc" ở đâu đó mà việc đếm không tới được.

Giả sử \(P(n)\) là một câu về số tự nhiên \(n\), và ta biết hai điều:

• \(P(0)\) đúng;
• với mọi \(n\), nếu \(P(n)\) đúng thì \(P(n + 1)\) đúng.

Muốn biết \(P(1000)\) có đúng không? Từ \(P(0)\) và điều thứ hai, \(P(1)\) đúng; từ \(P(1)\), \(P(2)\) đúng; ... sau đúng một nghìn bước, \(P(1000)\) đúng. Với mỗi \(n\) cụ thể, chuỗi này hữu hạn. Hai bước hữu hạn (một bước cơ sở, một bước chung cho mọi \(n\)) đủ phủ vô số trường hợp, vì chính việc đếm đã phủ mọi số tự nhiên.

Còn một cách nhìn khác, qua tính chất "không thể giảm mãi" của Chương 17. Giả sử có một số \(n\) làm \(P(n)\) sai. Trong các số như thế, lấy số nhỏ nhất, gọi là \(m\). Số \(m\) không thể là 0, vì \(P(0)\) đúng. Vậy \(m - 1\) là một số tự nhiên nhỏ hơn \(m\), nên \(P(m - 1)\) đúng (vì \(m\) là số nhỏ nhất làm \(P\) sai). Nhưng khi đó điều thứ hai cho \(P(m)\) đúng. Mâu thuẫn. Hai cách nhìn cho cùng một kết luận: lối lập luận domino hợp lệ.

Ký hiệu

Lối chứng minh trên gọi là quy nạp toán học (mathematical induction). Muốn chứng minh \(P(n)\) đúng với mọi số tự nhiên \(n \geq n_0\):

• bước cơ sở (base case): chứng minh \(P(n_0)\);
• bước quy nạp (inductive step): chứng minh rằng với mọi \(n \geq n_0\), \(P(n) \Rightarrow P(n + 1)\). Trong bước này, điều được giả sử, \(P(n)\), gọi là giả thiết quy nạp (induction hypothesis).

Quy nạp mạnh (strong induction) cho phép một giả thiết rộng hơn: để chứng minh \(P(n + 1)\), được giả sử \(P(k)\) đúng với mọi \(k\) từ \(n_0\) tới \(n\), chứ không chỉ \(P(n)\).

Tính chất "mỗi nhóm khác rỗng các số tự nhiên có một số nhỏ nhất" gọi là nguyên lý sắp thứ tự tốt (well-ordering principle).

Quy nạp đi đôi với định nghĩa đệ quy (Chương 12): định nghĩa đệ quy xây từng giá trị từ giá trị trước; quy nạp chứng minh từng điều từ điều trước. Hai ví dụ:

• giai thừa (factorial): \(0! = 1\) và \((n + 1)! = (n + 1) \cdot n!\), nên \(n! = 1 \cdot 2 \cdots n\) với \(n \geq 1\); chẳng hạn \(5! = 120\);
• dãy Fibonacci (Fibonacci sequence): \(F_1 = F_2 = 1\) và \(F_{n+2} = F_{n+1} + F_n\), cho \(1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \dots\); chẳng hạn \(F_{10} = 55\).

Làm bằng tay

Ví dụ 1 (tổng các số tự nhiên). Chứng minh \(1 + 2 + \dots + n = \frac{n(n + 1)}{2}\) với mọi \(n \geq 1\).

Bước cơ sở: với \(n = 1\), vế trái bằng 1, vế phải bằng \(\frac{1 \cdot 2}{2} = 1\).

Bước quy nạp: giả sử \(1 + 2 + \dots + n = \frac{n(n + 1)}{2}\). Cộng thêm \(n + 1\) vào hai vế:

\[ 1 + 2 + \dots + n + (n + 1) = \frac{n(n + 1)}{2} + (n + 1) = \frac{(n + 1)(n + 2)}{2}, \]

đúng là công thức với \(n + 1\) thay cho \(n\). Vậy công thức đúng với mọi \(n \geq 1\). \(\square\)

Quy nạp cho biết công thức đúng, nhưng không cho biết vì sao lại là \(\frac{n(n + 1)}{2}\). Hình dưới cho lý do ấy: hai bậc thang giống nhau ghép lại thành một hình chữ nhật \(n \times (n + 1)\), như cách ghép cặp ở Chương 1.

Bậc thang xanh có \(1 + 2 + 3 + 4 + 5\) ô; ghép với một bản sao lật ngược (màu cam), ta được hình chữ nhật \(5 \times 6\). Vậy tổng là \(\frac{5 \cdot 6}{2} = 15\).

Ví dụ 2 (tổng các số lẻ, nhìn lại). Chứng minh \(1 + 3 + \dots + (2n - 1) = n^2\). Bước cơ sở: \(1 = 1^2\). Bước quy nạp: giả sử tổng của \(n\) số lẻ đầu tiên là \(n^2\); cộng thêm số lẻ tiếp theo \(2n + 1\) được \(n^2 + 2n + 1 = (n + 1)^2\). \(\square\) Bước quy nạp này chính là lớp chữ L ở Chương 1: thêm \(2n + 1\) ô biến hình vuông \(n \times n\) thành hình vuông \((n + 1) \times (n + 1)\).

Ví dụ 3 (đoán trước, chứng minh sau). Tổng các lập phương có công thức gọn không? Thử:

\(n\)	1	2	3	4	5
\(1^3 + \dots + n^3\)	1	9	36	100	225
\(1 + \dots + n\)	1	3	6	10	15

Dòng trên là bình phương của dòng dưới: \(1 = 1^2\), \(9 = 3^2\), \(36 = 6^2\), \(100 = 10^2\), \(225 = 15^2\). Vậy đoán: \(1^3 + 2^3 + \dots + n^3 = \left(\frac{n(n + 1)}{2}\right)^2\). Quy nạp: bước cơ sở \(1 = 1^2\). Bước quy nạp: giả sử công thức đúng với \(n\); cộng thêm \((n + 1)^3\):

\[ \frac{n^2 (n + 1)^2}{4} + (n + 1)^3 = \frac{(n + 1)^2 \left(n^2 + 4n + 4\right)}{4} = \left(\frac{(n + 1)(n + 2)}{2}\right)^2 . \]

\(\square\) Để ý thứ tự: dữ liệu gợi ý công thức, quy nạp chứng minh nó. Quy nạp không tự tìm ra công thức.

Ví dụ 4 (\(2^n\) vượt \(n^2\)). Chương 12 đã thấy trên hình rằng \(2^n > n^2\) từ \(n = 5\). Giờ chứng minh.

Bước cơ sở: \(2^5 = 32 > 25 = 5^2\).

Bước quy nạp: giả sử \(2^n > n^2\) với một \(n \geq 5\). Khi đó \(2^{n+1} = 2 \cdot 2^n > 2n^2\). Còn cần \(2n^2 \geq (n + 1)^2\), tức \(n^2 \geq 2n + 1\). Với \(n \geq 5\), \(n^2 = n \cdot n \geq 5n = 2n + 3n > 2n + 1\). Vậy \(2^{n+1} > (n + 1)^2\). \(\square\)

Bước cơ sở phải chọn đúng chỗ. Bước quy nạp chạy được từ \(n = 3\), nhưng mệnh đề sai với \(n = 3\) (\(8 < 9\)) và với \(n = 4\) (\(16 = 16\), không lớn hơn). Cả hai bước đều phải đúng.

Ví dụ 5 (lát bảng bằng domino). Có bao nhiêu cách lát kín một bảng \(2 \times n\) ô bằng những quân domino \(1 \times 2\)? Gọi số cách là \(T(n)\). Nhìn cột đầu tiên: hoặc nó được lát bằng một quân đứng, và phần còn lại là bảng \(2 \times (n - 1)\); hoặc nó được lát bằng hai quân nằm, chiếm hai cột đầu, và phần còn lại là bảng \(2 \times (n - 2)\). Vậy

\[ T(n) = T(n - 1) + T(n - 2), \qquad T(1) = 1, \quad T(2) = 2 . \]

Đây là quy tắc của dãy Fibonacci: \(T(3) = 3\), \(T(4) = 5\), \(T(5) = 8\), ..., \(T(10) = 89\). Bằng quy nạp mạnh (bài B7), \(T(n) = F_{n+1}\) với mọi \(n \geq 1\).

Mọi cách lát bảng \(2 \times n\) với \(n = 1, 2, 3, 4\). Mỗi cách bắt đầu bằng một quân đứng (phần còn lại dài \(n - 1\)) hoặc hai quân nằm (phần còn lại dài \(n - 2\)): \(1, 2, 3, 5\) cách.

Ví dụ 6 (tháp Hà Nội). Trò chơi tháp Hà Nội (Tower of Hanoi) có ba cọc và \(n\) đĩa khác cỡ, ban đầu xếp trên cọc thứ nhất, đĩa lớn ở dưới. Mỗi bước được chuyển một đĩa trên cùng sang cọc khác, nhưng không được đặt đĩa lớn lên đĩa nhỏ. Cần chuyển cả chồng sang cọc thứ ba.

Gọi \(M(n)\) là số bước ít nhất. Với \(n = 1\): \(M(1) = 1\). Với \(n\) đĩa: chuyển \(n - 1\) đĩa trên sang cọc giữa (\(M(n - 1)\) bước), chuyển đĩa lớn nhất sang cọc thứ ba (1 bước), rồi chuyển \(n - 1\) đĩa lên trên nó (\(M(n - 1)\) bước). Vậy \(M(n) = 2M(n - 1) + 1\), và bài C3 cho thấy không thể làm ít bước hơn.

Chuyển \(n\) đĩa bằng cách chuyển \(n - 1\) đĩa hai lần và đĩa lớn nhất một lần: \(M(n) = 2M(n - 1) + 1\).

Từ \(1, 3, 7, 15, 31\), đoán \(M(n) = 2^n - 1\). Quy nạp: \(M(1) = 1 = 2^1 - 1\); nếu \(M(n) = 2^n - 1\) thì \(M(n + 1) = 2(2^n - 1) + 1 = 2^{n+1} - 1\). \(\square\)

Ví dụ 7 (quy nạp mạnh: phân tích ra thừa số nguyên tố). Chứng minh mọi số nguyên \(n \geq 2\) là tích của các số nguyên tố (một số nguyên tố cũng coi là tích của một thừa số).

Bước cơ sở: \(2\) là số nguyên tố. Bước quy nạp mạnh: giả sử mọi số từ 2 tới \(n\) đều là tích các số nguyên tố; xét \(n + 1\). Nếu \(n + 1\) là số nguyên tố, xong. Nếu không, \(n + 1 = a b\) với \(2 \leq a, b \leq n\). Theo giả thiết quy nạp mạnh, \(a\) và \(b\) đều là tích các số nguyên tố, nên \(n + 1 = ab\) cũng vậy. \(\square\)

Quy nạp thường không đủ ở đây: biết \(n\) là tích các số nguyên tố chẳng giúp gì cho \(n + 1\), vì các thừa số \(a\), \(b\) của \(n + 1\) có thể là bất kỳ số nào nhỏ hơn. Đây là phần "tồn tại" của định lý cơ bản của số học ở Chương 8.

Ví dụ 8 (vòng lặp trong máy tính). Một chương trình tính \(1 + 2 + \dots + n\) bằng vòng lặp:

s = 0
for k in range(1, n + 1):
    s = s + k

Vì sao nó đúng? Vì câu "sau lượt lặp thứ \(k\), \(s = 1 + 2 + \dots + k\)" đúng với mọi \(k\): đúng trước lượt đầu (với \(k = 0\), \(s = 0\)), và nếu đúng sau lượt thứ \(k\) thì lượt tiếp theo cộng thêm \(k + 1\) nên nó đúng sau lượt thứ \(k + 1\). Một câu như thế, giữ nguyên qua mỗi lượt lặp, gọi là bất biến vòng lặp (loop invariant). Kiểm chứng một vòng lặp là một chứng minh quy nạp; người viết phần mềm dùng nó, dù ít khi gọi tên.

Ranh giới

Mọi con ngựa cùng màu? "Chứng minh": với \(n = 1\), một con ngựa thì cùng màu với chính nó. Giả sử mọi nhóm \(n\) con ngựa đều cùng màu; xét \(n + 1\) con. Bỏ con cuối, \(n\) con còn lại cùng màu; bỏ con đầu, \(n\) con còn lại cùng màu; hai nhóm có chung các con ở giữa, nên cả \(n + 1\) con cùng màu. Chỗ sai: khi \(n = 1\), xét 2 con, bỏ con cuối còn con đầu, bỏ con đầu còn con cuối, và hai nhóm này không có con nào chung. Bước quy nạp hỏng đúng ở bước từ 1 lên 2, và một mắt xích hỏng là đủ làm đổ cả chuỗi.

Quên bước cơ sở. Xét câu "\(n + 1 < n\)". Bước quy nạp đúng: nếu \(n + 1 < n\) thì cộng 1 hai vế được \((n + 1) + 1 < n + 1\). Nhưng câu sai với mọi \(n\), vì không có quân domino đầu tiên nào đổ. Bước quy nạp đúng mà không có bước cơ sở thì không chứng minh được gì.

Quy nạp chứng minh, không phát minh. Muốn quy nạp, phải có sẵn điều cần chứng minh. Công thức tổng các lập phương được đoán từ bảng số, rồi mới được chứng minh. Quy nạp là công cụ kiểm chứng, không phải công cụ khám phá; phần khám phá cần quan sát, thử nghiệm, và đôi khi là một hình vẽ.

Quy nạp chỉ đi trên các bậc rời rạc. Nó dựa vào việc mỗi số tự nhiên có một số "kế tiếp". Các số thực không có số kế tiếp: không có số thực nào ngay sau 0. Vì vậy không thể quy nạp trực tiếp trên \(\mathbb{R}\); những câu "với mọi số thực" cần công cụ khác, và Phần IV sẽ xây những công cụ ấy.

Phát biểu chặt chẽ

Định lý 1 (nguyên lý quy nạp). Cho \(P(n)\) là một vị từ trên các số tự nhiên và \(n_0\) là một số tự nhiên. Nếu \(P(n_0)\) đúng, và với mọi \(n \geq n_0\), \(P(n) \Rightarrow P(n + 1)\), thì \(P(n)\) đúng với mọi \(n \geq n_0\).

Chứng minh (từ nguyên lý sắp thứ tự tốt). Giả sử ngược lại, nhóm các số \(n \geq n_0\) làm \(P(n)\) sai là khác rỗng. Theo Nguyên lý 3, nhóm ấy có số nhỏ nhất \(m\). Vì \(P(n_0)\) đúng nên \(m > n_0\), tức \(m - 1 \geq n_0\). Vì \(m\) nhỏ nhất, \(P(m - 1)\) đúng, nên theo giả thiết \(P(m)\) đúng. Mâu thuẫn. \(\square\)

Định lý 2 (nguyên lý quy nạp mạnh). Nếu \(P(n_0)\) đúng, và với mọi \(n \geq n_0\), từ "\(P(k)\) đúng với mọi \(k\) mà \(n_0 \leq k \leq n\)" suy ra \(P(n + 1)\), thì \(P(n)\) đúng với mọi \(n \geq n_0\).

Chứng minh. Áp dụng Định lý 1 cho vị từ \(Q(n)\): "\(P(k)\) đúng với mọi \(k\) mà \(n_0 \leq k \leq n\)". \(Q(n_0)\) chính là \(P(n_0)\). Nếu \(Q(n)\) đúng thì theo giả thiết \(P(n + 1)\) đúng, nên \(Q(n + 1)\) đúng. Vậy \(Q(n)\) đúng với mọi \(n \geq n_0\), và \(Q(n)\) kéo theo \(P(n)\). \(\square\)

Nguyên lý 3 (sắp thứ tự tốt). Mỗi nhóm khác rỗng các số tự nhiên có một số nhỏ nhất.

Nguyên lý 3 và Định lý 1 thật ra tương đương: mỗi cái suy ra được cái kia. Một trong hai phải được nhận như một tính chất nền của các số tự nhiên, phản ánh đúng cách chúng được tạo ra: bắt đầu từ 0, mỗi lần thêm 1, và không có gì khác.

Mệnh đề 4. Với mọi \(n \geq 1\), \(1 + 2 + \dots + n = \frac{n(n + 1)}{2}\). (Ví dụ 1.)

Mệnh đề 5. Với mọi \(n \geq 5\), \(2^n > n^2\). (Ví dụ 4.)

Mệnh đề 6. Mọi số nguyên \(n \geq 2\) là tích của các số nguyên tố. (Ví dụ 7.)

Sợi chỉ

• S5. Rời rạc và liên tục. Quy nạp là công cụ đặc trưng của thế giới rời rạc: nó cần một bước "kế tiếp", mà các số tự nhiên có và các số thực không có. Đếm ở Chương 4 tạo ra các số tự nhiên; quy nạp là mặt logic của cùng việc đếm ấy.
• S4. Cục bộ và toàn cục. Bước quy nạp chỉ nói về hai số liền nhau, một thông tin hoàn toàn cục bộ, vậy mà cùng với bước cơ sở nó cho một kết luận về mọi số. Chuyện ngựa cùng màu cho thấy một mắt xích cục bộ hỏng là đủ phá kết luận toàn cục.
• S1. Bất biến qua biến đổi. Bất biến vòng lặp là một điều giữ nguyên qua mỗi lượt lặp, như những bất biến ở bàn cờ cắt góc của Chương 1; quy nạp là cách chứng minh nó thật sự giữ nguyên.
• S6. Biểu diễn khác nhau của cùng một cấu trúc. Số cách lát bảng \(2 \times n\) và dãy Fibonacci là một; tổng \(1 + \dots + n\) là một công thức và là nửa hình chữ nhật.

Tóm tắt

• Quy nạp toán học: bước cơ sở chứng minh \(P(n_0)\), bước quy nạp chứng minh \(P(n) \Rightarrow P(n + 1)\) với mọi \(n \geq n_0\); khi đó \(P(n)\) đúng với mọi \(n \geq n_0\).
• Nó hợp lệ vì mọi số tự nhiên đạt được từ số đầu bằng cách cộng 1 lặp lại; tương đương, vì mỗi nhóm khác rỗng các số tự nhiên có số nhỏ nhất.
• Quy nạp mạnh cho giả sử mọi trường hợp trước; nó cần khi bước tiếp theo phụ thuộc vào những trường hợp xa hơn, như phân tích ra thừa số nguyên tố.
• Định nghĩa đệ quy (giai thừa, Fibonacci, lũy thừa) và chứng minh quy nạp đi đôi với nhau.
• Cả hai bước đều cần: thiếu bước cơ sở hay hỏng một mắt xích (ngựa cùng màu) là kết luận sụp đổ; bước cơ sở phải đặt đúng chỗ.
• Quy nạp chứng minh công thức chứ không tìm ra công thức; công thức được đoán từ dữ liệu hay từ hình.
• Bất biến vòng lặp trong chương trình máy tính được kiểm chứng bằng quy nạp.

Bài tập

A. Tư duy

A1. Trong hình ảnh hàng domino, điều gì xảy ra nếu (a) quân đầu tiên đổ, nhưng có một chỗ hai quân đặt quá xa nhau; (b) mọi quân đều đặt đủ gần nhau, nhưng không ai đẩy quân đầu tiên? Hai tình huống ứng với việc thiếu bước nào của quy nạp?

Lời giải

(a) Các quân đổ tới chỗ hở rồi dừng; những quân sau chỗ hở vẫn đứng. Đó là bước quy nạp hỏng tại một \(n\): \(P(n)\) đúng mà \(P(n + 1)\) không được suy ra. Chuyện ngựa cùng màu hỏng đúng kiểu này, tại \(n = 1\).

(b) Không quân nào đổ, dù quân nào cũng "sẵn sàng" đẩy quân sau. Đó là thiếu bước cơ sở, như với câu "\(n + 1 < n\)".

A2. Vì sao không thể chứng minh một điều "với mọi số thực \(x \geq 0\)" bằng quy nạp theo kiểu "đúng với \(x\) thì đúng với \(x + 1\)"? Lập luận ấy thật ra chứng minh được gì?

Lời giải

Từ "đúng với 0" và "đúng với \(x\) thì đúng với \(x + 1\)", ta chỉ đi được tới \(0, 1, 2, 3, \dots\), tức các số tự nhiên. Các số như \(\frac12\) hay \(\sqrt2\) không bao giờ được chạm tới, vì không có bước nào đi từ một số tự nhiên tới chúng. Lập luận chỉ chứng minh điều ấy cho các số tự nhiên. Các số thực không có "số kế tiếp", nên hình ảnh hàng domino không áp dụng được.

A3. Một người nói: "Quy nạp là phương pháp để tìm ra công thức." Người ấy đúng hay sai? Hãy mô tả quá trình người ta thường đi tới một công thức như công thức tổng các lập phương.

Lời giải

Sai. Quy nạp chỉ kiểm chứng một công thức đã có. Quá trình thường gặp gồm ba bước: tính các trường hợp nhỏ và lập bảng; nhìn ra một mẫu hình (các tổng lập phương là bình phương của các tổng \(1 + \dots + n\)) và phát biểu thành một phỏng đoán; rồi chứng minh phỏng đoán bằng quy nạp. Bước giữa là phần sáng tạo, không có quy tắc máy móc nào bảo đảm thành công. Và như Chương 1 đã cảnh báo, mẫu hình có thể đánh lừa, nên bước thứ ba không bao giờ bị bỏ qua.

B. Tính toán

B1. Tính \(0!, 1!, \dots, 7!\) và \(F_1, F_2, \dots, F_{12}\).

Lời giải

\(0! = 1\), \(1! = 1\), \(2! = 2\), \(3! = 6\), \(4! = 24\), \(5! = 120\), \(6! = 720\), \(7! = 5040\).

\(F_1, \dots, F_{12}\): \(1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144\).

B2. Chứng minh bằng quy nạp: \(1 + 2 + 4 + \dots + 2^{n - 1} = 2^n - 1\) với mọi \(n \geq 1\). Kết quả này nói gì về số \(11\ldots1_2\) gồm \(n\) chữ số 1 trong hệ nhị phân (Chương 4)?

Lời giải

Bước cơ sở: \(1 = 2^1 - 1\). Bước quy nạp: giả sử \(1 + 2 + \dots + 2^{n-1} = 2^n - 1\); cộng thêm \(2^n\) được \(2^n - 1 + 2^n = 2^{n+1} - 1\). \(\square\)

Số \(11\ldots1_2\) gồm \(n\) chữ số 1 chính là \(1 + 2 + \dots + 2^{n-1}\), nên nó bằng \(2^n - 1\): cộng thêm 1 thì mọi chữ số 1 "nhớ" dần lên thành \(100\ldots0_2 = 2^n\).

B3. Chứng minh: \(1 \cdot 2 + 2 \cdot 3 + \dots + n(n + 1) = \frac{n(n + 1)(n + 2)}{3}\) với mọi \(n \geq 1\).

Lời giải

Bước cơ sở: \(1 \cdot 2 = 2 = \frac{1 \cdot 2 \cdot 3}{3}\). Bước quy nạp: giả sử công thức đúng với \(n\); cộng thêm \((n + 1)(n + 2)\):

\[ \frac{n(n + 1)(n + 2)}{3} + (n + 1)(n + 2) = \frac{(n + 1)(n + 2)(n + 3)}{3}. \]

\(\square\)

B4. Tính \(\frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \dots + \frac{1}{n(n + 1)}\) với \(n = 1, 2, 3, 4\), đoán công thức, rồi chứng minh bằng quy nạp.

Lời giải

Các tổng là \(\frac12\), \(\frac23\), \(\frac34\), \(\frac45\). Đoán: tổng bằng \(\frac{n}{n + 1}\).

Bước cơ sở: \(\frac{1}{1 \cdot 2} = \frac12\). Bước quy nạp: giả sử tổng tới \(n\) bằng \(\frac{n}{n + 1}\); cộng thêm \(\frac{1}{(n + 1)(n + 2)}\):

\[ \frac{n}{n + 1} + \frac{1}{(n + 1)(n + 2)} = \frac{n(n + 2) + 1}{(n + 1)(n + 2)} = \frac{(n + 1)^2}{(n + 1)(n + 2)} = \frac{n + 1}{n + 2}. \]

\(\square\)

B5. Chứng minh \(n! > 2^n\) với mọi \(n \geq 4\). Vì sao bước cơ sở không thể là \(n = 1\)?

Lời giải

Bước cơ sở: \(4! = 24 > 16 = 2^4\). Bước quy nạp: nếu \(n! > 2^n\) với \(n \geq 4\) thì \((n + 1)! = (n + 1) \cdot n! > (n + 1) \cdot 2^n \geq 2 \cdot 2^n = 2^{n+1}\). \(\square\)

Với \(n = 1, 2, 3\): \(1! = 1 < 2\), \(2! = 2 < 4\), \(3! = 6 < 8\). Mệnh đề sai ở đó, nên không thể lấy làm bước cơ sở, dù bước quy nạp vẫn chạy được từ \(n = 1\).

B6. Chứng minh bằng quy nạp: \(4^n - 1\) chia hết cho 3 với mọi \(n \geq 0\).

Lời giải

Bước cơ sở: \(4^0 - 1 = 0\), chia hết cho 3. Bước quy nạp: giả sử \(4^n - 1 = 3k\). Khi đó \(4^{n+1} - 1 = 4 \cdot 4^n - 1 = 4(4^n - 1) + 3 = 12k + 3 = 3(4k + 1)\). \(\square\)

B7. Với \(T(n)\) là số cách lát bảng \(2 \times n\) (Ví dụ 5), tính \(T(5)\) tới \(T(10)\) và chứng minh \(T(n) = F_{n+1}\) với mọi \(n \geq 1\).

Lời giải

\(T(5) = 8\), \(T(6) = 13\), \(T(7) = 21\), \(T(8) = 34\), \(T(9) = 55\), \(T(10) = 89\).

Quy nạp mạnh, với hai bước cơ sở: \(T(1) = 1 = F_2\) và \(T(2) = 2 = F_3\). Với \(n \geq 2\), giả sử \(T(k) = F_{k+1}\) với mọi \(k \leq n\). Khi đó \(T(n + 1) = T(n) + T(n - 1) = F_{n+1} + F_n = F_{n+2}\). \(\square\) Cần hai bước cơ sở vì mỗi giá trị phụ thuộc vào hai giá trị trước.

B8. (a) Tính \(M(1)\) tới \(M(5)\) của tháp Hà Nội. (b) Nếu mỗi giây chuyển một đĩa, chồng 20 đĩa cần bao lâu?

Lời giải

(a) \(1, 3, 7, 15, 31\).

(b) \(2^{20} - 1 = 1.048.575\) giây, tức khoảng \(\frac{1.048.575}{86.400} \approx 12{,}1\) ngày không nghỉ.

B9. Chương trình sau tính gì? Tìm một bất biến vòng lặp và dùng nó để chứng minh kết quả.

p = 1
for k in range(1, n + 1):
    p = p * k

Lời giải

Bất biến: sau lượt lặp thứ \(k\), \(p = k!\). Trước lượt đầu, \(p = 1 = 0!\). Nếu sau lượt thứ \(k\) có \(p = k!\), thì lượt tiếp theo nhân \(p\) với \(k + 1\), cho \((k + 1) \cdot k! = (k + 1)!\). Theo quy nạp, sau lượt cuối, \(p = n!\): chương trình tính giai thừa của \(n\).

B10. Tìm chỗ sai trong "chứng minh" sau: "Mọi số tự nhiên đều bằng 0. Dùng quy nạp mạnh. Với \(n = 0\): đúng. Giả sử mọi số từ 0 tới \(n\) đều bằng 0. Viết \(n + 1 = a + b\) với \(a\), \(b\) là hai số tự nhiên không vượt quá \(n\). Theo giả thiết, \(a = b = 0\), nên \(n + 1 = 0\)."

Lời giải

Bước "viết \(n + 1 = a + b\) với \(a, b \leq n\)" không làm được khi \(n = 0\): khi ấy \(n + 1 = 1\), và 1 không phải tổng của hai số tự nhiên cùng không vượt quá 0 (vì \(0 + 0 = 0\)). Bước quy nạp hỏng ngay ở mắt xích đầu tiên, từ 0 lên 1, giống chuyện ngựa cùng màu. Với \(n \geq 1\) thì cách viết ấy làm được, nhưng chuỗi đã đứt từ trước.

C. Phản ví dụ và chứng minh

C1. Chứng minh \(F_1 + F_2 + \dots + F_n = F_{n+2} - 1\) với mọi \(n \geq 1\).

Lời giải

Bước cơ sở: \(F_1 = 1 = 2 - 1 = F_3 - 1\). Bước quy nạp: giả sử \(F_1 + \dots + F_n = F_{n+2} - 1\). Cộng thêm \(F_{n+1}\): \(F_{n+2} - 1 + F_{n+1} = F_{n+3} - 1\), theo quy tắc \(F_{n+3} = F_{n+2} + F_{n+1}\). \(\square\)

C2. Chứng minh rằng mọi số tự nhiên \(n \geq 12\) viết được thành \(4a + 5b\) với \(a\), \(b\) là các số tự nhiên. Số 11 thì sao?

Lời giải

Bốn bước cơ sở: \(12 = 4 \cdot 3\), \(13 = 4 \cdot 2 + 5\), \(14 = 4 + 5 \cdot 2\), \(15 = 5 \cdot 3\). Bước quy nạp mạnh: với \(n \geq 15\), xét \(n + 1 \geq 16\). Khi đó \(n + 1 - 4 = n - 3 \geq 12\) và nhỏ hơn \(n + 1\), nên theo giả thiết quy nạp mạnh, \(n - 3 = 4a + 5b\). Vậy \(n + 1 = 4(a + 1) + 5b\). \(\square\)

Số 11 không viết được: với \(b = 0, 1, 2\), phần còn lại \(11\), \(6\), \(1\) đều không chia hết cho 4, và \(b \geq 3\) thì \(5b > 11\).

C3. Chứng minh rằng không thể giải tháp Hà Nội \(n\) đĩa bằng ít hơn \(2^n - 1\) bước.

Lời giải

Gọi \(L(n)\) là số bước ít nhất. Ta chứng minh \(L(n) \geq 2L(n - 1) + 1\). Đĩa lớn nhất phải di chuyển ít nhất một lần. Ngay trước lần di chuyển đầu tiên của nó, cả \(n - 1\) đĩa nhỏ hơn phải nằm trên một cọc khác (cọc nó không ở và cọc nó không tới), tức đã được chuyển cả chồng: ít nhất \(L(n - 1)\) bước. Sau lần di chuyển cuối cùng của đĩa lớn nhất tới cọc thứ ba, \(n - 1\) đĩa kia phải được chuyển lên trên nó: ít nhất \(L(n - 1)\) bước nữa. Cộng với ít nhất một bước của đĩa lớn nhất: \(L(n) \geq 2L(n - 1) + 1\).

Quy nạp: \(L(1) = 1 = 2^1 - 1\). Nếu \(L(n) \geq 2^n - 1\) thì \(L(n + 1) \geq 2(2^n - 1) + 1 = 2^{n+1} - 1\). Kết hợp với cách giải ở Ví dụ 6, số bước ít nhất đúng bằng \(2^n - 1\). \(\square\)

Câu hỏi để ngỏ

Suốt từ Chương 4, ta đã nói "nhóm các số tự nhiên", "\(x\) thuộc \(\mathbb{R}\)", "mỗi nhóm khác rỗng có một số nhỏ nhất" khá tùy tiện. Một "nhóm" như thế chính xác là gì? Có thể gom bất cứ thứ gì lại thành một nhóm, rồi coi nhóm ấy là một đối tượng toán học, không?