Chương 16: Chứng minh trực tiếp và chứng minh phản đảo¶

Câu hỏi mở đầu

Giờ ta nói được chính xác "với mọi". Nhưng làm sao chắc chắn một câu "với mọi" là đúng, khi không thể thử hết vô số trường hợp? Những lập luận của Phần I, như lập luận chẵn lẻ cho \(\sqrt2\), đã làm được điều đó bằng cách nào, và có những kiểu lập luận nào khác?

Vì sao một lập luận buộc người ta tin?¶

Thử vài số với biểu thức \(n^2 - n\):

\(n\)	1	2	3	4	5	6	7
\(n^2 - n\)	0	2	6	12	20	30	42

Kết quả nào cũng chẵn. Liệu có phải luôn luôn như vậy? Bảng không trả lời được: Chương 15 đã nhắc rằng bốn mươi trường hợp đúng của \(n^2 + n + 41\) vẫn không cứu được nó ở trường hợp thứ bốn mươi mốt. Muốn chắc chắn, cần một lý do đúng cho mọi \(n\) cùng một lúc.

Lý do ấy đây: \(n^2 - n = n \cdot (n - 1)\) là tích của hai số nguyên liền nhau, và trong hai số liền nhau luôn có một số chẵn. Một số chẵn nhân với bất kỳ số nguyên nào cũng ra số chẵn. Xong. Lập luận này không thử một số nào, vậy mà nó đúng cho mọi \(n\), vì mỗi bước của nó đúng cho mọi \(n\).

Đó là bản chất của một chứng minh: một chuỗi bước, mỗi bước buộc phải đúng nếu các bước trước đúng. Bài C3 của Chương 14 đã cho thấy vì sao một chuỗi như thế giữ được sự thật từ đầu tới cuối: nếu \(P \Rightarrow Q_1\), \(Q_1 \Rightarrow Q_2\), ..., \(Q_k \Rightarrow R\) đều đúng thì \(P \Rightarrow R\) đúng. Người đọc không cần tin người viết; họ chỉ cần kiểm từng bước. Chương này bàn về những cách xây một chuỗi như thế.

Định nghĩa là điểm tựa¶

Muốn chứng minh điều gì đó về số chẵn, phải biết chính xác "chẵn" là gì. Chương 15 đã viết: \(n\) chẵn khi tồn tại số nguyên \(k\) với \(n = 2k\). Tương tự, \(n\) lẻ khi tồn tại số nguyên \(k\) với \(n = 2k + 1\). Bằng hình ảnh, một số chẵn là những cặp; một số lẻ là những cặp cộng thêm một chấm thừa.

Với hình ảnh ấy, tổng của hai số lẻ tự nó nói ra kết quả. Mỗi số có một chấm thừa; hai chấm thừa ghép lại thành một cặp mới. Vậy tổng là toàn cặp, tức là số chẵn.

Hai số lẻ cộng lại thành số chẵn — Số lẻ là những cặp cộng một chấm thừa. Cộng hai số lẻ, hai chấm thừa ghép thành một cặp, nên tổng là số chẵn.

Bằng ký hiệu, cũng lập luận ấy viết như sau. Gọi hai số lẻ là \(a = 2k + 1\) và \(b = 2m + 1\). Khi đó

\[ a + b = 2k + 1 + 2m + 1 = 2(k + m + 1), \]

và vì \(k + m + 1\) là số nguyên, \(a + b\) chẵn. Để ý hai chữ khác nhau \(k\) và \(m\): hai số lẻ bất kỳ không cần có cùng "số cặp", nên phải đặt cho chúng hai tên riêng.

Đây là khuôn mẫu của một chứng minh trực tiếp: mở định nghĩa của giả thiết ra thành những đẳng thức, biến đổi chúng, rồi gói kết quả lại theo đúng hình dạng mà định nghĩa của kết luận đòi hỏi. Phần khó thường nằm ở bước cuối: nhìn ra rằng \(2k + 2m + 2\) có dạng "2 nhân một số nguyên".

Ký hiệu và cách viết¶

Chứng minh trực tiếp (direct proof) một câu \(P \Rightarrow Q\): giả sử \(P\) đúng, rồi đi từng bước tới \(Q\).

Chứng minh phản đảo (proof by contrapositive): chứng minh \(\lnot Q \Rightarrow \lnot P\) thay cho \(P \Rightarrow Q\). Hai câu này tương đương logic (Định lý 4 của Chương 14), nên chứng minh được câu này là chứng minh được câu kia.

Chứng minh chia trường hợp (proof by cases): chia mọi khả năng thành vài trường hợp phủ kín, chẳng hạn \(n\) chẵn và \(n\) lẻ, rồi chứng minh riêng cho từng trường hợp.

Chứng minh một câu "\(P\) khi và chỉ khi \(Q\)" gồm hai phần: chứng minh \(P \Rightarrow Q\) và chứng minh \(Q \Rightarrow P\). Mỗi chiều có thể dùng một cách khác nhau.

Một chứng minh viết tốt thường có ba nhịp:

nói rõ giả thiết và đặt tên cho mọi thứ sẽ dùng ("Giả sử \(a\) và \(b\) lẻ. Viết \(a = 2k + 1\), \(b = 2m + 1\) với \(k\), \(m\) nguyên.");
nói rõ mục tiêu ("Ta cần chỉ ra \(a + b = 2 \cdot (\text{một số nguyên})\).");
đi từng bước, mỗi bước nêu lý do, và kết thúc bằng việc chỉ ra mục tiêu đã đạt.

Ký hiệu \(\square\) ở cuối đánh dấu chứng minh đã xong. Sơ đồ dưới đây tóm tắt hai con đường chính.

flowchart LR
    A["Giả thiết P"] --> B["Mở định nghĩa"]
    B --> C["Biến đổi từng bước"]
    C --> D["Gói lại theo định nghĩa"]
    D --> E["Kết luận Q"]
    F["Giả sử không Q"] --> G["Biến đổi từng bước"]
    G --> H["Suy ra không P"]
    H -. "tương đương" .-> E

Làm bằng tay¶

Ví dụ 1 (thử trước, chứng minh sau). Chứng minh rằng \(n^2 - n\) chẵn với mọi số nguyên \(n\).

Bảng ở đầu chương gợi ý câu này đúng. Có hai cách chứng minh.

Cách chia trường hợp. Nếu \(n\) chẵn, viết \(n = 2k\); khi đó \(n^2 - n = 4k^2 - 2k = 2(2k^2 - k)\), chẵn. Nếu \(n\) lẻ, viết \(n = 2k + 1\); khi đó \(n^2 - n = 4k^2 + 4k + 1 - 2k - 1 = 2(2k^2 + k)\), chẵn. Mọi số nguyên đều chẵn hoặc lẻ (Bổ đề 2), nên hai trường hợp phủ kín.

Cách phân tích: \(n^2 - n = n(n - 1)\). Trong hai số liền nhau \(n - 1\) và \(n\), đúng một số chẵn; tích của nó với số kia là số chẵn. Lập luận này nhanh hơn, nhưng dựa vào điều "trong hai số liền nhau có một số chẵn", mà thật ra cũng là một chứng minh chia trường hợp.

Ví dụ 2 (khi đi thẳng bị tắc). Chứng minh rằng với số nguyên \(n\): nếu \(n^2\) chẵn thì \(n\) chẵn.

Thử đi thẳng: giả sử \(n^2 = 2k\). Làm gì tiếp? Lấy căn bậc hai được \(n = \sqrt{2k}\), và chẳng biết gì thêm về tính chẵn lẻ của nó. Con đường bị tắc, vì giả thiết "\(n^2\) chẵn" không cho một dạng nào dễ dùng của \(n\).

Đi theo phản đảo: chứng minh "nếu \(n\) không chẵn thì \(n^2\) không chẵn", tức "nếu \(n\) lẻ thì \(n^2\) lẻ". Giờ giả thiết cho một dạng cụ thể: \(n = 2k + 1\), nên \(n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1\), lẻ. Xong. Đây chính là Bổ đề 1 của Chương 11, giờ được gọi đúng tên.

Bài học: phản đảo có lợi khi giả thiết khó dùng mà phủ định của kết luận lại dễ dùng.

Ví dụ 3 (tính bắc cầu của chia hết). Chứng minh rằng nếu \(a \mid b\) và \(b \mid c\) thì \(a \mid c\).

Mở định nghĩa (Chương 8): có số nguyên \(k\) với \(b = k a\), và có số nguyên \(m\) với \(c = m b\). Mục tiêu: tìm một số nguyên \(t\) với \(c = t a\). Thay \(b\) vào: \(c = m (k a) = (m k) a\). Vậy \(t = m k\), là số nguyên. \(\square\)

Chẳng hạn \(3 \mid 12\) và \(12 \mid 60\) nên \(3 \mid 60\), với \(60 = 5 \cdot 12 = 5 \cdot (4 \cdot 3) = 20 \cdot 3\).

Ví dụ 4 (một bất đẳng thức). Với hai số không âm \(a\), \(b\), trung bình cộng (arithmetic mean) của chúng là \(\frac{a + b}{2}\), còn trung bình nhân (geometric mean) là \(\sqrt{ab}\). Thử vài cặp:

\(a\), \(b\)	\(\sqrt{ab}\)	\(\frac{a + b}{2}\)
4 và 9	6	\(6{,}5\)
2 và 8	4	5
1 và 100	10	\(50{,}5\)
7 và 7	7	7

Trung bình nhân không bao giờ vượt trung bình cộng, và hai bên bằng nhau khi \(a = b\). Chứng minh: vì bình phương của một số thực không âm (Chương 7),

\[ 0 \leq \left(\sqrt a - \sqrt b\right)^2 = a - 2\sqrt{ab} + b . \]

Chuyển vế được \(2\sqrt{ab} \leq a + b\), tức \(\sqrt{ab} \leq \frac{a + b}{2}\). Dấu bằng xảy ra khi \(\sqrt a - \sqrt b = 0\), tức \(a = b\).

Có một hình ảnh cho cùng sự thật ấy. Xếp bốn hình chữ nhật \(a \times b\) quanh một ô vuông ở giữa, ta được một hình vuông cạnh \(a + b\), và ô ở giữa có cạnh \(a - b\). So diện tích: \((a + b)^2 = 4ab + (a - b)^2 \geq 4ab\), và đó chính là bất đẳng thức trên sau khi lấy căn hai vế rồi chia cho 2.

Bốn hình chữ nhật trong một hình vuông, và hình vuông có diện tích lớn nhất trong các hình chữ nhật cùng chu vi — Bên trái: \((a + b)^2 = 4ab + (a - b)^2\), nên \((a + b)^2 \geq 4ab\). Bên phải: cùng chu vi, hình vuông có diện tích lớn hơn; đó là cùng bất đẳng thức, với \(a\), \(b\) là hai cạnh.

Hình bên phải là một hệ quả: trong các hình chữ nhật có cùng chu vi \(2(a + b)\), diện tích \(ab\) không vượt quá \(\left(\frac{a + b}{2}\right)^2\), diện tích của hình vuông cùng chu vi.

Ví dụ 5 (khi và chỉ khi). Chứng minh rằng với số nguyên \(n\): \(n\) chẵn khi và chỉ khi \(n^2\) chẵn.

Chiều thuận, trực tiếp: nếu \(n = 2k\) thì \(n^2 = 4k^2 = 2(2k^2)\), chẵn. Chiều ngược là Ví dụ 2, bằng phản đảo. Hai chiều dùng hai cách khác nhau, và điều đó hoàn toàn bình thường.

Ví dụ 6 (đọc một chứng minh). Đọc một chứng minh không phải là đọc lướt cho tới dấu \(\square\), mà là hỏi ở mỗi bước: bước này đúng vì đâu? Xét chứng minh sau của câu "nếu \(a\) chẵn và \(b\) lẻ thì \(a + b\) lẻ":

Vì \(a\) chẵn, có số nguyên \(k\) với \(a = 2k\).
Vì \(b\) lẻ, có số nguyên \(m\) với \(b = 2m + 1\).
Vậy \(a + b = 2k + 2m + 1 = 2(k + m) + 1\).
Vì \(k + m\) là số nguyên, \(a + b\) lẻ. \(\square\)

Người đọc kiểm như sau. Bước 1 dùng giả thiết và định nghĩa số chẵn. Bước 2 dùng giả thiết và định nghĩa số lẻ, và đặt một tên mới \(m\) chứ không dùng lại \(k\). Bước 3 chỉ dùng các luật của phép cộng và phép nhân (Chương 5). Bước 4 dùng định nghĩa số lẻ, vốn đòi một số nguyên, và tổng của hai số nguyên là số nguyên. Mỗi bước đều có lý do: một giả thiết, một định nghĩa, hay một điều đã chứng minh. Một bước không trả lời được câu hỏi "vì đâu" là chỗ lỗi thường nấp.

Ranh giới¶

Ví dụ không phải chứng minh. Bảng ở đầu chương gợi ý, nhưng không chứng minh. Một ví dụ chỉ chứng minh được một câu "tồn tại" (Chương 15).

Suy ra một điều đúng không chứng minh được gì. "Chứng minh" \(1 = 2\) như sau: giả sử \(1 = 2\); nhân hai vế với 0 được \(0 = 0\), một điều đúng; vậy \(1 = 2\). Lỗi nằm ở hướng đi: từ \(P\) suy ra một điều đúng thì không cho biết gì về \(P\), vì \(P \Rightarrow Q\) luôn đúng khi \(Q\) đúng (Chương 14). Đi ngược từ kết luận là một cách tốt để tìm ra chứng minh, như cách làm nháp; nhưng chứng minh viết ra phải đi xuôi từ giả thiết tới kết luận, hoặc mỗi bước đi ngược phải là một phép tương đương có thể lật lại. Trong Ví dụ 4, mọi bước đều lật lại được, nên cả chuỗi đi xuôi cũng đúng.

Lập luận vòng quanh. "Tổng hai số chẵn là số chẵn, vì cộng hai số chẵn thì được một số chẵn." Câu này lấy chính điều cần chứng minh làm lý do. Lập luận vòng quanh (circular reasoning) thường khó thấy hơn thế: điều cần chứng minh được dùng ở một bước giữa chừng, dưới một cái tên khác.

Chia ẩn cho 0. "Chứng minh" \(2 = 1\) ở Chương 9 trông như một chuỗi bước chặt chẽ, nhưng có một bước chia hai vế cho \(a - b\), đúng bằng 0. Mỗi bước phải đúng trong mọi trường hợp mà giả thiết cho phép.

Nhầm chiều. Chứng minh mệnh đề đảo không phải chứng minh mệnh đề gốc. Muốn chứng minh "nếu \(n\) chia hết cho 4 thì \(n\) chẵn", chứng minh "nếu \(n\) chẵn thì ..." là đi sai đường ngay từ đầu.

Một chữ cho hai thứ. Viết "\(a\) lẻ nên \(a = 2k + 1\), \(b\) lẻ nên \(b = 2k + 1\)" là ngầm cho rằng \(a = b\). Mỗi đại lượng mới cần một tên mới, trừ khi có lý do để chúng bằng nhau.

Phát biểu chặt chẽ¶

Định nghĩa 1. Số nguyên \(n\) là số chẵn nếu tồn tại số nguyên \(k\) với \(n = 2k\), là số lẻ nếu tồn tại số nguyên \(k\) với \(n = 2k + 1\).

Bổ đề 2. Mỗi số nguyên là số chẵn hoặc số lẻ, và không thể vừa chẵn vừa lẻ.

Chứng minh. Với \(n \geq 0\), chia có dư cho 2 (Chương 6) cho \(n = 2q + r\) với \(r = 0\) hoặc \(r = 1\), tức \(n\) chẵn hoặc lẻ. Với \(n < 0\), áp dụng điều vừa rồi cho \(-n\): nếu \(-n = 2q\) thì \(n = 2(-q)\); nếu \(-n = 2q + 1\) thì \(n = 2(-q - 1) + 1\). Nếu \(n\) vừa chẵn vừa lẻ, \(n = 2k = 2m + 1\), thì \(2(k - m) = 1\); nhưng \(2(k - m)\) bằng 0 hoặc có giá trị tuyệt đối ít nhất là 2, không thể bằng 1. \(\square\)

Mệnh đề 3. Tổng hai số lẻ là số chẵn.

Chứng minh. Như ở mục "Định nghĩa là điểm tựa": \((2k + 1) + (2m + 1) = 2(k + m + 1)\). \(\square\)

Mệnh đề 4. Tích hai số lẻ là số lẻ.

Chứng minh. Với \(a = 2k + 1\) và \(b = 2m + 1\):

\[ ab = 4km + 2k + 2m + 1 = 2(2km + k + m) + 1, \]

và \(2km + k + m\) là số nguyên. \(\square\)

Tích 5 nhân 7 trên lưới gồm ba khối chẵn và một ô — Mệnh đề 4 trên lưới \(5 \times 7\): ba khối \(4 \cdot 6\), \(4 \cdot 1\), \(1 \cdot 6\) đều có số ô chẵn, chỉ còn một ô ở góc. Đó là \(4km + 2k + 2m + 1\) với \(k = 2\), \(m = 3\).

Mệnh đề 5. Với số nguyên \(n\): nếu \(n^2\) chẵn thì \(n\) chẵn.

Chứng minh (phản đảo). Giả sử \(n\) không chẵn. Theo Bổ đề 2, \(n\) lẻ. Theo Mệnh đề 4 với \(a = b = n\), \(n^2\) lẻ, nên không chẵn (Bổ đề 2). \(\square\)

Mệnh đề 6. Với mọi số nguyên \(n\), \(n^2 - n\) chẵn.

Chứng minh (chia trường hợp). Như Ví dụ 1. \(\square\)

Mệnh đề 7. Với các số nguyên \(a\), \(b\), \(c\): nếu \(a \mid b\) và \(b \mid c\) thì \(a \mid c\).

Chứng minh. Như Ví dụ 3. \(\square\)

Mệnh đề 8 (bất đẳng thức trung bình cộng và trung bình nhân). Với mọi số thực \(a \geq 0\), \(b \geq 0\):

\[ \sqrt{ab} \leq \frac{a + b}{2}, \]

và dấu bằng xảy ra khi và chỉ khi \(a = b\).

Chứng minh. Như Ví dụ 4; chiều "dấu bằng chỉ khi \(a = b\)" là bài C2. \(\square\)

Sợi chỉ

S1. Bất biến qua biến đổi. Tính chẵn lẻ là một bất biến rất mạnh: nó bị giữ nguyên hay đổi theo những luật đơn giản khi cộng và nhân (Mệnh đề 3, 4), và chỉ riêng điều ấy đã đủ chứng minh những câu như Mệnh đề 5, cũng như đã đủ cho bàn cờ cắt góc ở Chương 1 và cho \(\sqrt2\) ở Chương 11.
S6. Biểu diễn khác nhau của cùng một cấu trúc. Số lẻ là "cặp cộng một" và là \(2k + 1\); tích hai số lẻ là một lưới và là một khai triển đại số; bất đẳng thức trung bình là một dòng tính và là bốn hình chữ nhật trong một hình vuông, như hình vuông nghiêng của Chương 11.
S3. Thứ tự của biến đổi. Một chứng minh có hướng: đi xuôi từ giả thiết tới kết luận. Đi ngược là cách tìm lời giải, không phải lời giải, trừ khi mọi bước đều lật lại được.

Tóm tắt¶

Một chứng minh là một chuỗi bước, mỗi bước buộc phải đúng nếu các bước trước đúng; nó đúng cho mọi trường hợp vì từng bước đúng cho mọi trường hợp.
Định nghĩa là điểm tựa: "chẵn" là \(2k\), "lẻ" là \(2k + 1\), "\(a \mid b\)" là \(b = k a\); chứng minh trực tiếp mở định nghĩa của giả thiết và gói lại theo định nghĩa của kết luận.
Chứng minh phản đảo chứng minh \(\lnot Q \Rightarrow \lnot P\) thay cho \(P \Rightarrow Q\); nó có lợi khi phủ định của kết luận dễ dùng hơn giả thiết, như với "\(n^2\) chẵn thì \(n\) chẵn".
Chứng minh chia trường hợp cần các trường hợp phủ kín; chứng minh "khi và chỉ khi" cần hai chiều.
Trung bình nhân không vượt trung bình cộng: \(\sqrt{ab} \leq \frac{a + b}{2}\), suy ra từ \(\left(\sqrt a - \sqrt b\right)^2 \geq 0\).
Lỗi thường gặp: chứng minh bằng ví dụ, suy từ kết luận ra điều đúng rồi cho là xong, lập luận vòng quanh, chia ẩn cho 0, nhầm chiều, dùng một chữ cho hai đại lượng.

Bài tập¶

A. Tư duy¶

A1. Một người nói: "Tôi đã cho máy kiểm tra \(n^2 - n\) chẵn với mọi \(n\) từ 1 tới một tỷ. Vậy là đã chứng minh xong." Người ấy đã có gì trong tay, và còn thiếu gì? Chứng minh ở Ví dụ 1 cho thêm điều gì ngoài sự chắc chắn?

Lời giải

Người ấy có một tỷ trường hợp đúng: một bằng chứng mạnh để tin rằng câu đúng, và một gợi ý tốt để đi tìm chứng minh. Nhưng câu nói về mọi số nguyên, gồm cả số âm và vô số số lớn hơn một tỷ; một phản ví dụ có thể nằm ở đó, như \(n^2 + n + 41\) ở Chương 1.

Chứng minh ở Ví dụ 1 cho thêm một lý do: \(n^2 - n = n(n - 1)\) là tích của hai số liền nhau. Lý do ấy giải thích vì sao kết quả luôn chẵn, và còn gợi ý những điều mới, chẳng hạn tích của ba số liền nhau thì sao (bài C3).

A2. "Đi ngược từ kết luận" có phải là một cách chứng minh hợp lệ không? Khi nào có, khi nào không?

Lời giải

Đi ngược từ kết luận là một cách rất tốt để tìm chứng minh: hỏi "muốn có điều này, cần điều gì?", rồi lại hỏi tiếp, cho tới khi gặp một điều đã biết. Nhưng một chứng minh phải đi xuôi: từ điều đã biết tới kết luận.

Chuỗi đi ngược trở thành chứng minh hợp lệ khi mỗi bước của nó là một phép tương đương, lật lại được, như trong Ví dụ 4: \(\sqrt{ab} \leq \frac{a + b}{2}\) tương đương \(2\sqrt{ab} \leq a + b\), tương đương \(0 \leq \left(\sqrt a - \sqrt b\right)^2\). Nếu có một bước chỉ đi được một chiều, như nhân hai vế với 0, thì chuỗi ấy không chứng minh được gì: từ \(1 = 2\) cũng suy ra được \(0 = 0\).

A3. Một người viết: "Giả sử \(a\) và \(b\) lẻ. Khi đó \(a = 2k + 1\) và \(b = 2k + 1\). Vậy \(a + b = 4k + 2 = 2(2k + 1)\), chẵn." Kết luận đúng, nhưng chứng minh sai ở đâu? Lỗi ấy có thể dẫn tới kết luận sai nào?

Lời giải

Dùng cùng một chữ \(k\) cho cả hai số là ngầm cho rằng \(a = b\). Chứng minh vì thế chỉ đúng cho trường hợp hai số lẻ bằng nhau, không cho hai số lẻ bất kỳ.

Cùng lỗi ấy có thể "chứng minh" một điều sai: "hiệu hai số lẻ luôn bằng 0", vì \(a - b = (2k + 1) - (2k + 1) = 0\). Nhưng \(5 - 3 = 2\).

B. Tính toán¶

B1. Thử với vài số, rồi chứng minh: tổng của ba số nguyên liên tiếp luôn chia hết cho 3.

Lời giải

Thử: \(1 + 2 + 3 = 6\), \(4 + 5 + 6 = 15\), \((-1) + 0 + 1 = 0\): đều chia hết cho 3.

Chứng minh: gọi ba số là \(n - 1\), \(n\), \(n + 1\). Tổng là \((n - 1) + n + (n + 1) = 3n\), chia hết cho 3. \(\square\) Đặt số ở giữa là \(n\) làm phép tính gọn nhất; đặt tên khéo cũng là một phần của chứng minh.

B2. Chứng minh: tích của hai số chẵn chia hết cho 4.

Lời giải

Viết hai số chẵn là \(2k\) và \(2m\). Tích của chúng là \(4km\), và \(km\) là số nguyên, nên tích chia hết cho 4. \(\square\)

B3. Thử với vài số lẻ, rồi chứng minh: nếu \(n\) lẻ thì \(n^2 - 1\) chia hết cho 8.

Lời giải

Thử: \(1^2 - 1 = 0\), \(3^2 - 1 = 8\), \(5^2 - 1 = 24\), \(7^2 - 1 = 48\): đều chia hết cho 8.

Chứng minh: \(n = 2k + 1\), nên \(n^2 - 1 = 4k^2 + 4k = 4k(k + 1)\). Theo Mệnh đề 6 (với \(k + 1\) thay cho \(n\)), \(k(k + 1) = (k + 1)^2 - (k + 1)\) chẵn, tức \(k(k + 1) = 2t\). Vậy \(n^2 - 1 = 8t\). \(\square\)

B4. Dùng phản đảo, chứng minh với số nguyên \(n\): (a) nếu \(n^2\) lẻ thì \(n\) lẻ; (b) nếu \(3n + 2\) lẻ thì \(n\) lẻ.

Lời giải

(a) Phản đảo: nếu \(n\) chẵn thì \(n^2\) chẵn. Với \(n = 2k\), \(n^2 = 2(2k^2)\). \(\square\)

(b) Phản đảo: nếu \(n\) chẵn thì \(3n + 2\) chẵn. Với \(n = 2k\), \(3n + 2 = 6k + 2 = 2(3k + 1)\). \(\square\) Đi thẳng từ "\(3n + 2\) lẻ" khó hơn nhiều, vì nó không cho một dạng dễ dùng của \(n\).

B5. Chứng minh bằng chia trường hợp: với mọi số nguyên \(n\), \(n^2\) chia cho 3 dư 0 hoặc 1 (không bao giờ dư 2).

Lời giải

Mọi số nguyên có một trong ba dạng \(3k\), \(3k + 1\), \(3k + 2\) (chia có dư cho 3). Trường hợp \(n = 3k\): \(n^2 = 3(3k^2)\), dư 0. Trường hợp \(n = 3k + 1\): \(n^2 = 3(3k^2 + 2k) + 1\), dư 1. Trường hợp \(n = 3k + 2\): \(n^2 = 9k^2 + 12k + 4 = 3(3k^2 + 4k + 1) + 1\), dư 1. \(\square\)

B6. Kiểm tra bất đẳng thức \(\sqrt{ab} \leq \frac{a + b}{2}\) với: (a) \(a = 3\), \(b = 12\); (b) \(a = 0\), \(b = 10\); (c) \(a = \frac14\), \(b = 4\).

Lời giải

(a) \(\sqrt{36} = 6 \leq 7{,}5\). (b) \(\sqrt0 = 0 \leq 5\). (c) \(\sqrt1 = 1 \leq \frac{17}{8} = 2{,}125\).

B7. (a) Trong các hình chữ nhật có chu vi 20, hình nào có diện tích lớn nhất? (b) Chứng minh rằng với mọi số thực \(x > 0\), \(x + \frac1x \geq 2\). Khi nào có dấu bằng?

Lời giải

(a) Hai cạnh \(a\), \(b\) có \(a + b = 10\). Theo Mệnh đề 8, \(\sqrt{ab} \leq 5\), tức \(ab \leq 25\), và dấu bằng khi \(a = b = 5\). Hình vuông \(5 \times 5\) có diện tích lớn nhất.

(b) Áp dụng Mệnh đề 8 với \(a = x\), \(b = \frac1x\): \(\sqrt{x \cdot \frac1x} = 1 \leq \frac{x + \frac1x}{2}\), tức \(x + \frac1x \geq 2\). Dấu bằng khi \(x = \frac1x\), tức \(x = 1\) (vì \(x > 0\)). \(\square\)

B8. Tìm chỗ sai trong "chứng minh" sau: "Mọi số nguyên đều chẵn. Thật vậy, lấy số nguyên \(n\) bất kỳ và đặt \(k = \frac{n}{2}\). Khi đó \(n = 2k\), nên \(n\) chẵn."

Lời giải

Định nghĩa đòi \(k\) là một số nguyên. Với \(n = 3\), \(k = \frac32\) không phải số nguyên, nên đẳng thức \(3 = 2 \cdot \frac32\) không chứng tỏ 3 chẵn. Mỗi chữ trong định nghĩa đều có vai trò; bỏ qua một điều kiện ("\(k\) nguyên") là làm hỏng cả chứng minh.

B9. Chứng minh với số nguyên \(n\): \(n\) chia hết cho 3 khi và chỉ khi \(n^2\) chia hết cho 3.

Lời giải

Chiều thuận, trực tiếp: nếu \(n = 3k\) thì \(n^2 = 3(3k^2)\).

Chiều ngược, phản đảo: nếu \(n\) không chia hết cho 3 thì \(n = 3k + 1\) hoặc \(n = 3k + 2\), và theo bài B5, \(n^2\) chia cho 3 dư 1, nên không chia hết cho 3. \(\square\)

B10. (a) Chứng minh: nếu \(d \mid a\) và \(d \mid b\) thì \(d \mid (a + b)\) và \(d \mid (a - b)\). (b) Suy ra rằng hai số nguyên liên tiếp \(n\) và \(n + 1\) không có ước chung nào lớn hơn 1.

Lời giải

(a) Viết \(a = kd\), \(b = md\). Khi đó \(a + b = (k + m)d\) và \(a - b = (k - m)d\). \(\square\)

(b) Nếu \(d\) là một ước chung dương của \(n\) và \(n + 1\), theo (a) thì \(d \mid (n + 1) - n = 1\), nên \(d = 1\). \(\square\)

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

C1. Chứng minh rằng tích của ba số lẻ là số lẻ. Suy ra rằng nếu một tích của ba số nguyên là số chẵn thì ít nhất một thừa số chẵn.

Lời giải

Với ba số lẻ \(a\), \(b\), \(c\): theo Mệnh đề 4, \(ab\) lẻ; lại theo Mệnh đề 4, \((ab) \cdot c\) lẻ. \(\square\)

Câu thứ hai là phản đảo của câu thứ nhất: "nếu cả ba thừa số đều không chẵn (tức đều lẻ) thì tích không chẵn (tức lẻ)". Theo luật De Morgan, phủ định của "ít nhất một thừa số chẵn" là "mọi thừa số đều lẻ". \(\square\)

C2. Chứng minh rằng với \(a\), \(b \geq 0\), nếu \(\sqrt{ab} = \frac{a + b}{2}\) thì \(a = b\).

Lời giải

Nếu \(\sqrt{ab} = \frac{a + b}{2}\) thì \(a + b - 2\sqrt{ab} = 0\), tức \(\left(\sqrt a - \sqrt b\right)^2 = 0\). Bình phương của một số thực bằng 0 chỉ khi số ấy bằng 0, nên \(\sqrt a = \sqrt b\), và bình phương hai vế được \(a = b\). \(\square\)

C3. Chứng minh rằng với mọi số nguyên \(n\), \(n^3 - n\) chia hết cho 6. (Gợi ý: phân tích \(n^3 - n\) thành tích ba số liên tiếp.)

Lời giải

\(n^3 - n = n(n^2 - 1) = (n - 1) n (n + 1)\), tích của ba số nguyên liên tiếp.

Chia hết cho 2: trong ba số ấy có \(n - 1\) và \(n\) là hai số liền nhau, nên có một số chẵn.

Chia hết cho 3: chia \(n\) cho 3. Nếu \(n = 3k\) thì \(3 \mid n\). Nếu \(n = 3k + 1\) thì \(n - 1 = 3k\). Nếu \(n = 3k + 2\) thì \(n + 1 = 3(k + 1)\). Trường hợp nào cũng có một thừa số chia hết cho 3.

Vậy \(n^3 - n = 2s\) và \(3 \mid 2s\). Vì 3 là số nguyên tố không chia hết 2, theo bổ đề Euclid (Chương 8) thì \(3 \mid s\), tức \(s = 3t\) và \(n^3 - n = 6t\). \(\square\)

Câu hỏi để ngỏ¶

Có những điều mà đi thẳng không tới được, nhất là khi phải chứng minh một điều là không thể, hay không tồn tại: không có phân số nào bình phương bằng 2, không có số nguyên tố lớn nhất. Không thể thử mọi phân số hay kiểm mọi số nguyên tố. Vậy làm sao chứng minh "không có"?