Phương pháp quy nạp toán học

Quy nạp toán học là phương pháp chứng minh hay dùng trong toán học, thường gặp nhất khi làm việc với các số tự nhiên hoặc với một dãy nào đó.

Nguyên tắc

Nguyên tắc cơ bản là: trước hết ta chứng minh khẳng định đã cho đúng với phần tử đầu tiên; với các số nguyên dương, đó thường là n = 1. Điều này chứng minh bằng cách thay trực tiếp. Ở bước tiếp theo, gọi là bước quy nạp, ta chứng minh mệnh đề kéo theo “nếu khẳng định đúng với n = a thì nó cũng đúng với n = a + 1”.

Từ hai bước này, ta suy ra biểu thức đã cho đúng với mọi n (thuộc tập hợp mà ta đang xét). Vì sao vậy? Ban đầu ta chứng minh được biểu thức đúng với n = 1. Đồng thời ta biết rằng nếu biểu thức đúng với n = a thì nó cũng đúng với n = a + 1. Chọn a = 1: ta biết biểu thức đúng với a = 1, do đó nó cũng đúng với a + 1 = 2. Lúc này ta biết biểu thức đúng với a = 2. Nhưng vì nó cũng đúng với a + 1, nên nó phải đúng với 2 + 1 = 3. Và cứ như vậy.

Ví dụ thứ nhất

Ví dụ thứ nhất rất đơn giản. Ta chứng minh rằng nếu cộng 2 vào một số chẵn bất kì thì ta lại được một số chẵn. Vì ta làm việc với số nguyên dương, ta viết số chẵn tổng quát là 2n, trong đó n là số nguyên dương. Thay n bằng một số nguyên dương bất kì, ta đều được một số chẵn, điều này thấy ngay. Quan hệ chia hết được viết bằng một vạch thẳng đứng như sau:

$$2\mid 2n$$

Cách viết này nghĩa là biểu thức 2n chia hết cho 2. Khi đã biết cách viết quan hệ chia hết, ta có thể viết điều cần chứng minh bằng quy nạp toán học.

$$2\mid 2n+2;n\in {\mathbb{N}}^{\ast }$$

Đó là điều cần chứng minh trong ví dụ thứ nhất: 2n + 2 chia hết cho 2. Điều này đúng với đề bài bằng lời ban đầu: “nếu cộng 2 vào một số chẵn bất kì thì ta lại được một số chẵn”.

Ở bước thứ nhất của quy nạp (bước cơ sở), ta chứng minh khẳng định đúng với phần tử đầu tiên, tức là với 1. Thay n = 1 vào biểu thức:

$$\begin{array}{rcl}2& \mid & 2\cdot 1+2\\ 2& \mid & 4\end{array}$$

4 chia hết cho 2, nên khẳng định đúng với phần tử đầu tiên. Tiếp theo là bước quy nạp: ta phải chứng minh rằng nếu khẳng định đúng với phần tử thứ a thì nó cũng đúng với phần tử thứ (a + 1). Trước hết, ta giả sử khẳng định đúng với n = a (giả thiết quy nạp):

$$2\mid 2a+2$$

Ta giả sử biểu thức này đúng và sẽ dùng nó khi xây dựng chứng minh. Bây giờ ta muốn chứng minh rằng

$$2\mid 2(a+1)+2.$$

Ta đã làm gì? Ta viết (a + 1) vào chỗ của a. Dấu ngoặc rất quan trọng; viết như sau là sai: 2a + 1 + 2. Ta không cộng 1 vào cả biểu thức, mà thật sự thay a bằng biểu thức lớn hơn nó 1 đơn vị, tức là (a + 1). Nhân phá ngoặc, ta biến đổi biểu thức thành:

$$\begin{array}{rcl}2& \mid & 2(a+1)+2\\ 2& \mid & 2a+2+2\end{array}$$

Bây giờ ta nói thêm một chút về quan hệ chia hết. Nếu có hai số, chẳng hạn p và q, cùng chia hết cho một số, chẳng hạn r, thì tổng của chúng cũng chia hết cho r. Ta có:

$$(r\mid p\wedge r\mid q)\Rightarrow r\mid (p+q)$$

Chẳng hạn, có thể thay p = 8, q = 20 và r = 4. Ta thấy cả 8 và 20 đều chia hết cho 4, và tổng của chúng 8 + 20 = 28 cũng chia hết cho 4.

Ta dùng điều này trong ví dụ của mình thế nào? Tách vế phải thành hai số p và q như sau:

$$p=2a+2;q=2$$

Số q, tức là 2, hiển nhiên chia hết cho 2. Biểu thức p cũng chia hết cho 2, vì giả thiết quy nạp cho ta biết điều đó: biểu thức p trùng khớp với giả thiết quy nạp mà ta giả sử là đúng. Nếu p chia hết cho 2 và q cũng chia hết cho 2 thì tổng của chúng cũng chia hết cho 2.

Nói thêm về giả thiết quy nạp. Ban đầu ta đã nói rằng ta giả sử

$$2\mid 2a+2.$$

Vì vậy, khi gặp biểu thức 2a + 2 trong quá trình chứng minh, ta có thể nói nó chia hết cho 2, chính vì đó là giả thiết quy nạp. Đây thường là bước khó nhất của quy nạp toán học: hiểu được khi nào và vì sao có thể dùng giả thiết quy nạp.

Đến đây phép quy nạp kết thúc, chứng minh đã hoàn tất, định lí đúng.

Nếu muốn, bạn có thể tách theo cách khác mà không cần dùng giả thiết quy nạp: p = 2n và q = 2 + 2. Số q = 4 hiển nhiên chia hết cho 2, và p = 2n cũng vậy, vì chia cho 2 ta được số n, là một số nguyên dương, tức là số nguyên. Lại được hai biểu thức cùng chia hết cho 2, nên tổng của chúng cũng chia hết cho 2.

Dù theo cách nào, ta cũng đã chứng minh được rằng

1. biểu thức đã cho đúng với n = 1,
2. nếu biểu thức đúng với n thì nó cũng đúng với n + 1.

Từ đây ta suy ra:

• Biểu thức đúng với n = 1.
• Nếu đúng với n thì phải đúng với n + 1, tức là với 1 + 1; vậy biểu thức đúng với n = 2.
• Nếu đúng với n thì phải đúng với n + 1, tức là với 2 + 1; vậy biểu thức đúng với n = 3.
• Nếu đúng với n thì phải đúng với n + 1, tức là với 3 + 1; vậy biểu thức đúng với n = 4.
• Nếu đúng với n thì phải đúng với n + 1, tức là với 4 + 1; vậy biểu thức đúng với n = 5.
• …

Ví dụ thứ hai

Tiếp theo, ta dùng quy nạp toán học để chứng minh một khẳng định đơn giản:

$$2^n\ge 2n;n\in {\mathbb{N}}^{\ast }.$$

Trước hết là bước cơ sở: kiểm tra khẳng định có đúng với n = 1 không, vì 1 là phần tử đầu tiên của tập số nguyên dương mà ta lấy n từ đó.

$$\begin{array}{rcl}{2}^1& \ge & 2\cdot 1\\ 2& \ge & 2\end{array}$$

Điều này hiển nhiên đúng. Bây giờ chuyển sang bước quy nạp: ta phải kiểm tra rằng nếu khẳng định đúng với n = a thì nó cũng đúng với n = a + 1. Vậy giả thiết quy nạp là

$$2^a\ge 2a$$

và ta muốn chứng minh:

$$2^{a+1}\ge 2(a+1)$$

Trước hết, ta biến đổi vế trái theo các quy tắc tính luỹ thừa, còn vế phải thì chỉ cần nhân phá ngoặc.

$$2\cdot 2^a\ge 2a+2$$

Ở vế trái, ta thay phép nhân bằng phép cộng, vế phải giữ nguyên.

$$2^a+2^a\ge 2a+2$$

Bây giờ ta dùng giả thiết quy nạp. Giả thiết quy nạp là mệnh đề mà ta giả sử là đúng. Mỗi vế của bất đẳng thức là tổng của hai số hạng. Đồng thời ta biết rằng

$$\begin{array}{rcl}{2}^a& \ge & 2a\\ 2^a& \ge & 2.\end{array}$$

Dòng thứ nhất là giả thiết quy nạp, còn khẳng định thứ hai là hiển nhiên (giá trị nhỏ nhất của 2^a đạt được khi a = 1 và bằng đúng 2). Vậy ta biết rằng hai số hạng ở vế trái lần lượt lớn hơn hoặc bằng hai số hạng ở vế phải. Như vậy ta đã chứng minh bằng quy nạp rằng nếu biểu thức đúng với a thì nó cũng đúng với (a + 1); và vì biểu thức cũng đúng với 1, nên biểu thức đã cho đúng.

Ví dụ thứ ba

Ta thử chứng minh khẳng định sau:

$$3\mid n\Rightarrow 3\mid n^2;n\in {\mathbb{N}}^{\ast }$$

Phát biểu bằng lời: nếu n chia hết cho 3 thì n² cũng chia hết cho 3. Nếu n không chia hết cho 3 thì biểu thức hiển nhiên đúng (theo định nghĩa mệnh đề kéo theo), nên ta chỉ xét các trường hợp n chia hết cho 3. Các số đó tạo thành dãy số nguyên dương a_i = 3, 6, 9, 12, 15, … Từ đây trở đi, ta chỉ làm việc trong dãy a_i này.

Ta bắt đầu chứng minh quy nạp bằng bước cơ sở, tức là kiểm tra khẳng định đúng với phần tử đầu tiên. Xin nhắc lại rằng ta đang làm việc trong dãy a_i, nên ta lấy phần tử đầu tiên của dãy này, tức là a₁, bằng 3. Với số 3, biểu thức đúng:

$$3\mid 3\Rightarrow 3\mid 3^2$$

Bây giờ chuyển sang bước quy nạp. Ta thấy dãy a_i có thể viết dưới dạng 3n, trong đó n là số nguyên dương; tức là mỗi phần tử lớn hơn phần tử đứng trước 3 đơn vị. Giả sử biểu thức đúng với n; ta phải chứng minh nó cũng đúng với (n + 3), là công thức cho phần tử tiếp theo của dãy mà ta đang xét. Trước hết viết giả thiết quy nạp:

$$3\mid n\Rightarrow 3\mid n^2$$

rồi viết điều cần chứng minh

$$3\mid (n+3)\Rightarrow 3\mid (n+3{)}^2.$$

Khai triển biểu thức trong ngoặc ở vế phải theo hằng đẳng thức:

$$3\mid (n+3)\Rightarrow 3\mid n^2+6n+9.$$

Gần xong rồi. Ở vế trái là một biểu thức chắc chắn chia hết cho 3, vì theo giả thiết n chia hết cho 3 (ta chỉ làm việc với các số thuộc dãy a_i), và 3 cũng chia hết cho 3. Ở vế phải, trước hết là n², theo giả thiết quy nạp chia hết cho 3. Thật vậy, ta biết n chia hết cho 3, và giả thiết quy nạp nói rằng nếu n chia hết cho 3 thì n² cũng chia hết cho 3:

$$3\mid n\Rightarrow 3\mid n^2$$

Tiếp theo là số hạng 6n, hiển nhiên chia hết cho 3. Có thể hình dung điều này như rút gọn phân thức:

$$\frac{6n}{3}=2n$$

Biến n là một số nguyên dương nào đó, nên tích 2n cũng là số nguyên dương; tức là chia cho 3 ta được một số nguyên dương, và do đó 6n phải chia hết cho 3. Cuối cùng, số 9 cũng chia hết cho 3. Biểu thức đúng với phần tử đầu tiên và ở bước quy nạp, vậy biểu thức đúng.

Số dấu ngoặc trong biểu thức

Ví dụ cuối cùng hơi khác thường. Ta thử chứng minh khẳng định rằng số dấu ngoặc trong một biểu thức đơn giản luôn là số chẵn, để bạn thấy quy nạp toán học có thể dùng trong những bối cảnh hoàn toàn khác chứ không chỉ với số tự nhiên. Trước hết, ta phải định nghĩa biểu thức đơn giản là gì. Biểu thức đơn giản là:

• một số tự nhiên,
• nếu p là biểu thức đơn giản thì (p²) cũng là biểu thức đơn giản,
• nếu p và q là biểu thức đơn giản thì (p + q) cũng là biểu thức đơn giản.

Vậy những biểu thức đơn giản là: 12, 54, (5 + 6), (12 + 7), (6²), ((5 + 6)²). Ngược lại, những biểu thức sau không phải là biểu thức đơn giản:

• 1 + 2 → thiếu cặp ngoặc ngoài cùng,
• (1 + 2 → thiếu ngoặc phải,
• 13² → thiếu cặp ngoặc ngoài cùng,
• (1 + 2 + 3) → thiếu ngoặc, cách viết đúng phải là (1 + (2 + 3))

Một biểu thức đơn giản có thể được tạo ra chẳng hạn như sau. Ban đầu ta chọn biểu thức đơn giản (a + b). Bây giờ thay a bằng biểu thức đơn giản a = (c + d), ta được ((c + d) + b), rồi thay b bằng 3: ((c + d) + 3). Thay c bằng 10: ((10 + d) + 3), và cuối cùng thay d bằng (5²): ((10 + (5²)) + 3). Phải giữ đúng các dấu ngoặc, nếu không kết quả sẽ sai.

Bây giờ ta chứng minh rằng biểu thức đơn giản chứa một số chẵn dấu ngoặc (số 0 cũng là số chẵn).

Ở bước cơ sở, ta chọn một phần tử đầu tiên. Ở đây, phần tử đầu tiên là biểu thức đơn giản nhất, tức là một số tự nhiên bất kì. Vậy ta đặt

$$j=n;n\in \mathbb{N}.$$

Biểu thức j có 0 dấu ngoặc, nên phần tử đầu tiên thoả mãn. Ở bước quy nạp, ta giả sử có hai biểu thức đơn giản p và q, cả hai đều có số chẵn dấu ngoặc. Khi đó ta phải chứng minh rằng các biểu thức đơn giản (p + q) và (p²) cũng có số chẵn dấu ngoặc.

Trước hết là phép cộng. Ta định nghĩa thêm hàm số z(q) cho biết số dấu ngoặc của biểu thức q. Khi đó biểu thức (p + q) có z(p) + z(q) + 2 dấu ngoặc, tức là nhiều hơn tổng số dấu ngoặc của hai biểu thức p và q đúng 2 dấu ngoặc. Theo giả thiết quy nạp, z(p) và z(q) đều chẵn; cộng ba số chẵn, ta lại được một số chẵn. Trong trường hợp này, mệnh đề đúng.

Bây giờ đến luỹ thừa. Lại có giả thiết quy nạp: biểu thức đơn giản p chứa một số chẵn dấu ngoặc. Khi đó biểu thức (p²) chứa z(p) + 2 dấu ngoặc, tức là lại nhiều hơn biểu thức p đúng 2 dấu ngoặc. Trường hợp này ta cũng cộng các số chẵn, nên kết quả là số chẵn.

Mệnh đề đúng với phần tử đầu tiên và đúng ở bước quy nạp, vì vậy mệnh đề đúng.