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 đề $P(n)$ đúng với mọi số tự nhiên $n$, ta thực hiện theo hai bước sau:
Chứng minh $P(n)$ đúng với $n=1$.
Giả sử $P(n)$ đúng với $1, 2, cdots, n$. Chứng minh $P(n+1)$ đúng.
Ví dụ 1. Cho $x$ thỏa $x+dfrac{1}{x}$ là số nguyên. Chứng minh rằng $x^n+dfrac{1}{x^n}$ là số nguyên với mọi $n$.
Lời giải.
Ta có $x + dfrac{1}{x}$ là số nguyên đúng (theo giả thiết).
Giả sử $x^k + dfrac{1}{x^k}$ là số nguyên với mọi $k = overline{1,n}$. Ta cần chứng minh $x^{n+1} + dfrac{1}{x^{n+1}}$.
$(x^{n+1} + dfrac{1}{x^{n+1}} = (x+dfrac{1}{x})(x^n + dfrac{1}{n}) – (x^{n-1}+dfrac{1}{x^{n-1}})$.
Theo giả thiết quy nạp thì $x^{n+1} + dfrac{1}{x^{n+1}}$ là số nguyên.
Vậy ta có $x^n + dfrac{1}{x^n}$ là số nguyên với mọi $n$.
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 đề $P(n)$ đúng với mọi $n$, ta làm như sau:
Chứng minh $P(1), P(2), cdots, P(k)$ đúng.
Giả sử $P(n)$ đúng. Ta chứng minh $P(n+k)$ đúng.
Ví dụ 2. Chứng minh rằng với mọi số tự nhiên $M$ tồn tại số tự nhiên $n$ và cách chọn các dấu $+$ hoặc $-$ sao cho
$M = pm 1^2 pm 2^2 cdots pm n^2$.
Lời giải.
Khi $M = 1, 2, 3, 4$ ta có $1 = 1^2$, $2 = -1^2-2^2-3^2+4^2$, $3 = -1^2+2^2$ và $4 = 1^2-2^2-3^2+4^2$.
Giả sử đúng với $M$, tức là tồn tại $n$ thỏa $M = pm 1^2 pm 2^2 cdots pm n^2$, khi đó $M + 4 = pm 1^2 pm 2^2 cdots pm n^2 +(n+1)^2-(n+2)^2-(n+3)^2 + (n+4)^2$.
Ví dụ 3. Chứng minh rằng với mọi số tự nhiên $n$ thì phương trình $a^2 + b^2 = c^n$ luôn có nghiệm trong tập các số nguyên dương.
Lời giải.
Rõ ràng nếu $n=1, 2$ 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à $a, b, c$ với $n$ nào đó, tức là $a^2 + b^2 = c^n$.
Khi đó với $n+2$ thì xét $(ac), (bc), c$: $(ac)^2+(bc)^2 = c^2 (a^2+b^2) = c^{n+2}$.
$(ac, bc, c$ là nghiệm.
Vậy phương trình luôn có nghiệm với mọi $n$.
Dạng kế tiếp là Quy nạp lùi được phát biểu như sau:
Chứng minh $P(a_i)$ đúng với dãy $(a_i)$ là dãy con tăng thực sự của tập các số tự nhiên.
Giả sử $P(n)$ đúng, chứng minh $P(n-1)$ đú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 $a_1, a_2 ,…, a_8$ sao cho 2 số $a_i, a_j$ bất kì $(i < j)$ thì mọi số trong dãy nằm giữa $a_i$ và $a_j$ đều khác $dfrac{a_i + a_j}{2}$. b) Chứng minh rằng với $N$ số nguyên dương đầu tiên $1, 2, …, N$ luôn tìm được cách sắp thành dãy $a_1, a_2, …, a_N$ sao cho dãy thỏa mãn điều kiện như câu a). 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 = 2^k$ thì luôn tồn tại một cách xếp thỏa đề bài.
Nếu $k = 1$, 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 $n = 2^k$, cách xếp đó là $a_1, a_2, …, a_n$. Ta chứng minh tồn tại một cách xếp với $n = 2^{k+1}$. Thật vậy xét hoán vị $(2a_1, 2a_2,…, 2a_n, 2a_1-1, 2a_2-1, …, 2a_n-1)$ là một hoán vị của $1, 2, …, 2^{k+1}$. Ta chứng minh hoán vị trên thỏa đề bài.
Ta có nếu $a_i, a_j in {2a_1, 2a_2, …, 2a_n}$ theo giả thiết quy nạp không có số nào nằm giữa $a_i, a_j$ bằng $dfrac{1}{2}(a_i+a_j)$.
Nếu $a_i in {2a_1, …, 2a_n}, a_j in {2a_1-1, 2a_2-1, …, 2a_n-1}$ thì $dfrac{1}{2}(a_i +a_j)$ không phải số nguyên.
Nếu $a_i, a_j in {2a_1-1, 2a_2-1, …, 2a_n-1}$ theo giả thiết quy nạp thì cũng có số nào nằm giữa $a_i, a_j$ bằng $dfrac{1}{2}(a_i + a_j)$.
Vậy bài toán đúng với $n = 2^k$.(1) Bước 2. Nếu bài toán đúng với $n$, ta chứng minh bài toán đúng với $n-1$.
Xét các số $a_1, a_2, …, a_n$ là một hoán vị thỏa đề bài của $1,2,…,n$.
Khi đó nếu xóa bất kì số nào trong các số $a_1, …, a_n$ thì dãy còn lại vẫn thỏa điều kiện. (2) 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: $dfrac{a_1+a_2 + cdots+a_n}{n} geq sqrt[n]{a_1a_2cdots a_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 $n$ lớn nhất thỏa mãn các điều kiện sau:
$n$ không chia hết cho 3;
Bảng vuông $n times n$ ô không thể được phủ kín bằng 1 quân tetramino $1 times 4$ và các quân trimino kích thước $1 times 3$. 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ó $n$ số tự nhiên từ 1 đến $n$ được viết thành một dòng theo một thứ tự nào đó. Mỗi bước thực hiện biến đổi như sau: nếu số đầu tiên là $k$ thì $k$ số đầu tiên sẽ được viết theo thứ tự ngược lại. Chứng minh rằng sau hữu hạn bước thì số đầu tiên của dòng là số 1.
Bài 4. Trong cuộc họp có $2n$ ($n geq 2$) người, một số người bắt tay nhau và người ta đếm được có $n^2+1$ cái bắt tay. Chứng minh rằng có $n$ bộ ba, mà mỗi bộ ba đôi một bắt tay nhau.
Bài 5. Chứng minh rằng với mọi số tự nhiên $n$ tồn tại các số nguyên $x, y, z$ phân biệt sao cho $x^2+y^2+z^2 = 14^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.
Like this:
Like
Loading…
Related
Điều hướng bài viết