Bài học

Quy nạp mạnh và phân rã số nguyên

Mục tiêu bài học

Sau bài này, em có thể nhận ra khi bước k+1 cần nhiều trường hợp trước và viết giả thiết quy nạp mạnh đúng phạm vi. Năng lực cần đạt không dừng ở việc nhớ một công thức: em phải nhận ra tín hiệu của bài toán, giải thích vì sao chọn phương pháp và trình bày một chuỗi suy luận có thể kiểm tra được.

Kiến thức cần có

Mệnh đề, quy nạp cơ bản, chia hết, AM-GM, dãy số và tổng hữu hạn.

Chuẩn HSG so với bài chuẩn

Bài chuẩn thường dùng đúng một giả thiết P(k) để chứng minh P(k+1). Mở rộng dành cho HSG: quy nạp mạnh dùng toàn bộ các trường hợp trước; quy nạp Cauchy kết hợp bước nhân đôi và bước lùi để phủ mọi n. Nội dung mở rộng được giới thiệu từng bước trong bài; em không cần biết trước ngoài các kiến thức đã nêu ở trên.

Câu hỏi mở đầu

Để chứng minh mọi n≥2 là tích các số nguyên tố, khi n+1 hợp số ta cần biết điều gì về các ước nhỏ hơn? Hãy dừng lại một phút và viết ra hai điều: dữ kiện nào đang khống chế bài toán, và trường hợp đặc biệt nào đáng thử trước. Câu trả lời ban đầu chưa cần hoàn chỉnh; mục đích là tập thói quen nhìn cấu trúc trước khi tính.

Công cụ và cách phát hiện

Quy nạp mạnh giả sử P(2),P(3),…,P(k) đồng thời đúng. Nó phù hợp khi đối tượng k+1 được tách thành nhiều phần nhỏ hơn không cố định, nên một giả thiết P(k) đơn lẻ không đủ. Khi đọc đề, ta không hỏi ngay “dùng công thức nào”, mà hỏi “điều kiện nào phải được tận dụng hết”. Một lời giải HSG tốt thường có ba lớp: nhận diện cấu trúc, chọn phép biến đổi bảo toàn điều kiện, rồi kiểm tra trường hợp biên hoặc dấu bằng. Ba lớp này phải xuất hiện rõ trong bài viết, không được giấu sau một chuỗi tính toán.

Cách làm an toàn là dự đoán kết quả bằng một trường hợp cân bằng hoặc đối xứng, sau đó thử biến đổi ngược từ đích. Nếu phép biến đổi tạo ra điều kiện mới, phải ghi điều kiện ấy ngay tại chỗ. Nếu dùng một bất đẳng thức, phải nêu điều kiện áp dụng và trường hợp đẳng thức. Nếu giải phương trình, mọi nghiệm nhận được sau bình phương, đặt ẩn hoặc đổi biểu diễn đều phải thử lại. Đây là phần trình bày thường quyết định điểm số trong bài HSG.

Bước k+1 có thể gọi nhiều mệnh đề trước, không chỉ P(k).

Ví dụ mẫu thứ nhất

Ví dụ

Ví dụ 1 — Tích các số nguyên tố

1
Chứng minh mọi số nguyên n≥2 là số nguyên tố hoặc tích các số nguyên tố.
2
Đề không chỉ định sẵn phép biến đổi. Muốn đi tiếp, ta phải đọc điều kiện, dự đoán trường hợp đẳng thức hoặc cấu trúc nghiệm, rồi mới chọn công cụ. Nếu biến đổi trước khi có định hướng, lời giải rất dễ dài hoặc mất điều kiện.
3
Nếu n+1 hợp số, tách thành ab với 2≤a,b≤n và dùng giả thiết cho cả a,b.
4
Cơ sở n=2 đúng. Giả sử mệnh đề đúng với mọi số từ 2 đến k. Xét k+1. Nếu k+1 nguyên tố thì xong. Nếu hợp số, $k+1=ab$ với $2le a,ble k$ . Theo giả thiết mạnh, a và b đều là nguyên tố hoặc tích các số nguyên tố; nhân hai phân tích được phân tích của k+1. Vậy mệnh đề đúng với mọi n≥2.
Cơ sở n=2 đúng. Giả sử mệnh đề đúng với mọi số từ 2 đến k. Xét k+1. Nếu k+1 nguyên tố thì xong. Nếu hợp số, $k+1=ab$ với $2le a,ble k$. Theo giả thiết mạnh, a và b đều là nguyên tố hoặc tích các số nguyên tố; nhân hai phân tích được phân tích của k+1. Vậy mệnh đề đúng với mọi n≥2.
5
Sau khi có kết quả, cần đối chiếu lại điều kiện và trường hợp xảy ra dấu bằng hoặc nghiệm đặc biệt. Không dùng định lý đang chứng minh như một sự thật có sẵn.
6
Từ đây xây dựng sự tồn tại của phân tích thừa số nguyên tố, chưa bàn tính duy nhất.

Ví dụ mẫu thứ hai

Ví dụ

Ví dụ 2 — Dãy Fibonacci và chặn mũ

1
Với $F_1=F_2=1$ , $F_{n+2}=F_{n+1}+F_n$ , chứng minh $F_n<2^{n-1}$ với n≥2.
Với $F_1=F_2=1$, $F_{n+2}=F_{n+1}+F_n$, chứng minh $F_n<2^{n-1}$ với n≥2.
2
Đề không chỉ định sẵn phép biến đổi. Muốn đi tiếp, ta phải đọc điều kiện, dự đoán trường hợp đẳng thức hoặc cấu trúc nghiệm, rồi mới chọn công cụ. Nếu biến đổi trước khi có định hướng, lời giải rất dễ dài hoặc mất điều kiện.
3
Bước n+2 cần đồng thời hai chặn của n+1 và n.
4
Cơ sở: $F_2=1<2$ . Giả sử với mọi j từ 2 đến k+1, $F_j<2^{j-1}$ . Khi đó $F_{k+2}=F_{k+1}+F_k<2^k+2^{k-1}<2^{k+1}$ . Do đó mệnh đề đúng tại k+2. Vậy $F_n<2^{n-1}$ với mọi n≥2.
Cơ sở: $F_2=1<2$. Giả sử với mọi j từ 2 đến k+1, $F_j<2^{j-1}$. Khi đó $F_{k+2}=F_{k+1}+F_k<2^k+2^{k-1}<2^{k+1}$. Do đó mệnh đề đúng tại k+2. Vậy $F_n<2^{n-1}$ với mọi n≥2.
5
Sau khi có kết quả, cần đối chiếu lại điều kiện và trường hợp xảy ra dấu bằng hoặc nghiệm đặc biệt. Không thay $2^k+2^{k-1}$ bằng $2^k$ .
Sau khi có kết quả, cần đối chiếu lại điều kiện và trường hợp xảy ra dấu bằng hoặc nghiệm đặc biệt. Không thay $2^k+2^{k-1}$ bằng $2^k$.
6
Tìm một chặn sắc hơn bằng số vàng là nội dung mở rộng sau khóa.

Tự kiểm chứng lời giải

Trước khi chuyển sang luyện tập, em hãy kiểm tra lại hai ví dụ theo bốn câu hỏi. Một: mọi phép chia, căn, logarit hoặc ẩn phụ có kèm điều kiện chưa. Hai: kết quả trung gian có đúng chiều và đúng miền không. Ba: trường hợp dấu bằng hoặc nghiệm biên có thật sự thỏa đề gốc không. Bốn: kết luận cuối đã trả lời đủ điều đề hỏi chưa. Với Giả sử đúng cho toàn bộ các chỉ số trước, một cách kiểm tra tốt là thay một giá trị đơn giản vào cả biểu thức ban đầu lẫn biểu thức sau biến đổi; hai kết quả phải khớp. Cách thử số không thay cho chứng minh, nhưng nó phát hiện nhanh lỗi dấu, lỗi hệ số và nghiệm ngoại lai. Sau đó, hãy thử kể lại ý tưởng bằng ba câu ngắn: tín hiệu nào xuất hiện, công cụ nào được chọn, và vì sao điều kiện của đề làm công cụ ấy trở nên sắc. Nếu ba câu này rõ ràng, em đã nắm phương pháp chứ không chỉ chép lại phép tính.

Một vòng kiểm tra độc lập nữa là đổi cách biểu diễn: với đại số, thử phân tích hoặc khai triển ngược; với hình học, đối chiếu bằng tọa độ, độ dài hay thể tích; với xác suất, cộng các trường hợp để kiểm tra tổng; với dãy và giải tích, thế vài giá trị hoặc so giới hạn biên. Em cần ghi rõ phép kiểm tra đã xác nhận điều gì và điều gì vẫn phải dựa vào chứng minh. Thói quen này giúp phân biệt một đáp số có vẻ hợp lý với một lời giải thật sự kín kẽ.

Luyện tập có hướng dẫn

Ở ba câu vừa rồi, điều quan trọng hơn đáp số là lý do chọn bước đầu. Em nên tự nói thành lời: “Tôi chọn Giả sử đúng cho toàn bộ các chỉ số trước vì dữ kiện của đề tạo đúng cấu trúc cần thiết”. Nếu không nói được câu đó, hãy quay lại sơ đồ phương pháp trước khi làm phần độc lập.

Luyện tập độc lập

Lỗi thường gặp

Viết “giả sử đúng với n” nhưng không chỉ ra dòng nào dùng giả thiết đó

Kiểm tra nhanh

Tóm tắt và nối bài

Điều cần giữ lại là: dùng quy nạp mạnh khi cấu trúc mới phân rã thành nhiều đối tượng nhỏ hơn có chỉ số không cố định. Khi tự luyện, em hãy ghi riêng “tín hiệu nhận dạng” ở lề bài giải; sau vài bài, việc chọn công cụ sẽ nhanh hơn hẳn. Bài sau học bước lùi Cauchy để chứng minh AM-GM cho mọi số lượng biến.