B. MỘT SỐ KIẾN THỨC VÀ VÍ DỤ MỞ RỘNG

§1. NGUYÊN LÝ QUY NẠP

Trong phần mở rộng này, chúng tôi phát biểu lại Nguyên lí thứ tự tốt mà các bạn vẫn thường dùng, và chứng minh Nguyên lí quy nạp (tổng quát hơn) thường được sử dụng.

1.1. Nguyên lí thứ tự tốt (The well-ordering principle)

Giả sử A là tập con khác rỗng của tập các số nguyên dương. Lúc đó, A chứa một phần tử bé nhất.

Nguyên lí này còn được gọi là Tiên đề thứ tự.

Ví dụ 1.

Trên mặt phẳng vô hạn được kẻ ô vuông người ta điền các số tự nhiên vào các ô vuông sao cho mỗi số tùy ý luôn bằng trung bình cộng của 4 số tự nhiên trong 4 ô vuông có cạnh chung với ô vuông chứa nó. Chứng minh rằng khi đó tất cả các số được điền đều bằng nhau.

Giải.

Xét tập hợp tất cả các số được điền. Đây là một tập con không rỗng của tập hợp các số tự nhiên.

Theo nguyên lí đã nêu ở trên, tập hợp này có một phần tử nhỏ nhất mà ta kí hiệu là a. Giả sử rằng các số được điền không bằng nhau tất cả. Như vậy sẽ có một ô chứa số a mà trong 4 ô có cạnh chung với nó sẽ có ít nhất một ô chứa số b $\neq$ a. Giả sử các số ở 3 ô còn lại có cạnh chung với ô chứa số a này là c, d và e. Theo giả sử về sự nhỏ nhất của số a, ta có b > a và c, d, e $\geq$ a. Do đó $\large \frac{1}{4}$(b + c + d + e) > a, trái với giả thiết của bài toán là a trung bình cộng của b, c, d và e.

1.2. Nguyên lí quy nạp (The principle of induction)

Nguyên lí quy nạp sau đây được phát biểu dưới dạng tập hợp, được chứng minh bằng phương pháp phản chứng và sử dụng nguyên lí thứ tự tốt.

Giả sử Q là tập hợp con của tập các số nguyên sao cho

(a) k $\in$ Q;

(b) n $\in$ Q suy ra (n + 1) $\in$ Q với mọi n $\geq$ k.

Lúc đó ta có

(c) mọi số nguyên lớn hơn hoặc bằng k đều thuộc Q.

Chứng minh.

Giả sử ngược lại rằng (c) không đúng.

Đặt S = {x $\in$ N, x $\geq$ k, x $\notin$ Q}. Như vậy, S là tập con khác rỗng của tập các số nguyên dương, theo giả thiết phản chứng vừa nêu. Từ Nguyên lí thứ tự tốt, có thể gọi m là phần tử bé nhất của S.

Theo (a), phải có m > k, suy ra m - 1 $\geq$ k. Vì m - 1 < m nên ta có m – 1 $\notin$ S, hay m – 1 $\in$ Q. Do đó, theo (b), m $\in$ Q, điều này mâu thuẫn.

1.3. Một số bài toán khó

Ví dụ 2. (Trích đề thi HSG Quốc gia, 1978)

Chứng minh rằng với mọi số nguyên dương n, số được thành lập bởi $3^{n}$ chữ số giống nhau thì chia hết cho $3^{n}$.

Giải:

Giả sử số đã cho là

Ta sẽ chứng minh A chia hết cho $3^{n}$. (*)

Với n = 1 ta có $\overline{aaa}$ = 111a $\vdots$ 3. Vậy phát biểu (*) đúng với n = 1.

Giả sử phát biểu (*) đúng với n = k, tức là ta có :

Ta có : Do đó :

Đẳng thức trên xảy ra do giả thiết quy nạp ngoài ra

Vậy phát biểu (*) cũng đúng với n = k + 1, do đó nó đúng với mọi số nguyên dương n.

Ví dụ 3.

Cho 1< a < b. Ta lập hai dãy {$u_{n}$} và {$v_{n}$} như sau:

$u_{1}$ = b, $v_{1}$ = a,

Chứng minh rằng:

Giải.

Do a > 1, b > 1 nên dễ thấy {$u_{n}$}, {$v_{n}$} là các dãy số dương. Ta có:

Ta sẽ chứng minh

Do $u_{1}$ + $v_{1}$ = b + a > 2 nên (1) đúng khi n = 1. Giả sử bất đẳng thức (1) đúng khi n = k, tức là:

Khi đó,

Vậy (1) đã được chứng minh (theo nguyên lí quy nạp).

Bây giờ ta chứng minh rằng với mọi n = 1, 2, ..., ta có

Với n = 1, bất đẳng thức (2) đúng, bởi vì

Giả sử bất đẳng thức (2) đúng đến n = k, tức là:

Khi n = k + 1 ta có:

Từ (1) ta được:

Theo nguyên lí quy nạp, ta có điều phải chứng minh.

Ví dụ 4.

Chứng minh rằng với mọi số tự nhiên n ta có:

Giải.

Bất đẳng thức đúng khi n = 1.

Giả sử bất đẳng thức đúng khi n = k, tức là

Ta phải chứng minh bất đẳng thức đúng với n= k + 1, nghĩa là:

Theo giả thiết quy nạp ta phải chứng minh:

Điều này có thể chứng minh được dễ dàng vì:

Từ đó suy ra điều phải chứng minh.