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_2\cdots a_n}$.

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 $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.