Trong bài này, chúng ta tiếp tục tìm hiểu thêm và phương pháp quy nạp. Ngoài dạng quy nạp như đã biết ta còn một số dạng quy nạp khác như: Quy nạp mạnh, quy nạp bước nhảy, quy nạp lùi.
Quy nạp mạnh được phát biểu như sau: Để chứng minh mệnh đề
- Chứng minh
đúng với . - Giả sử
đúng với . Chứng minh đúng.
Ví dụ 1. Cho
Lời giải.
- Ta có
là số nguyên đúng (theo giả thiết). - Giả sử
là số nguyên với mọi . Ta cần chứng minh . .- Theo giả thiết quy nạp thì
là số nguyên.
- Vậy ta có
là số nguyên với mọi .
Dạng kế tiếp là Quy nạp bước nhảy được phát biểu như sau: Chứng minh mệnh đề
- Chứng minh
đúng. - Giả sử
đúng. Ta chứng minh đúng.
Ví dụ 2. Chứng minh rằng với mọi số tự nhiên
Lời giải.
- Khi
ta có , , và . - Giả sử đúng với
, tức là tồn tại thỏa , khi đó .
Ví dụ 3. Chứng minh rằng với mọi số tự nhiên
Lời giải.
- Rõ ràng nếu
thì phương trình luông có nghiệm nguyên dương. - Giả sử phương trình có nghiệm nguyên dương là
với nào đó, tức là .- Khi đó với
thì xét : . là nghiệm.
- Khi đó với
- Vậy phương trình luôn có nghiệm với mọi
.
Dạng kế tiếp là Quy nạp lùi được phát biểu như sau:
- Chứng minh
đúng với dãy là dãy con tăng thực sự của tập các số tự nhiên. - Giả sử
đúng, chứng minh đúng.
Ví dụ 4.
a) Hãy chỉ ra cách sắp 8 số nguyên dương đầu tiên 1, 2, …, 8 thành một dãy
b) Chứng minh rằng với
Lời giải.
a) Một cách xếp thỏa đề bài là 26481537.\
b)
Bước 1.Ta chứng minh bằng quy nạp với
- Nếu
, hiển nhiên đúng.
Giả sử luôn tồn tại một cách xếp thỏa đề bài với , cách xếp đó là .
Ta chứng minh tồn tại một cách xếp với .
Thật vậy xét hoán vị là một hoán vị của . Ta chứng minh hoán vị trên thỏa đề bài.- Ta có nếu
theo giả thiết quy nạp không có số nào nằm giữa bằng . - Nếu
thì không phải số nguyên. - Nếu
theo giả thiết quy nạp thì cũng có số nào nằm giữa bằng .
- Ta có nếu
Vậy bài toán đúng với
Bước 2. Nếu bài toán đúng với
Xét các số
Khi đó nếu xóa bất kì số nào trong các số
Từ (1) và (2) ta có điều cần chứng minh.
Quy nạp lùi cũng là một trong những cách chứng minh bất đẳng thức Cauchy tổng quát:
Các bạn tự làm thử nhé.
Trên đây là một số dạng quy nạp thường gặp trong chứng minh toán. Tùy theo tình huống mà ta sử dụng cho phù hợp, các bạn cần làm thêm nhiều bài tập để rèn luyện.
Bài tập rèn luyện.
Bài 1. Ta gọi tổng các số tự nhiên từ 1 đến n là số tam giác. Chứng minh rằng tồn tại vô hạn các số tam giác đồng thời là số chính phương.
Bài 2. (Chọn đội tuyển PTNK 2014)Tìm số nguyên dương
không chia hết cho 3;- Bảng vuông
ô không thể được phủ kín bằng 1 quân tetramino và các quân trimino kích thước . Trong phép phủ các quân tetramino và trimino được phép quay dọc nhưng không được phép chườm lên nhau hoặc nằm ngoài ra bảng vuông.
Bài 3. Có
Bài 4. Trong cuộc họp có
Bài 5. Chứng minh rằng với mọi số tự nhiên
Bài 6. Trong một giải đấu tennis có 10 người tham dự, hai đối thủ gặp nhau đúng một trận. Chứng minh rằng, sau khi kết thúc giải có thể sắp xếp các tay vợt thành một hàng mà người đứng trước thắng người đứng sau.