Chứng minh bằng quy nạp

Định nghĩa

Quy nạp và đệ quy là hai khái niệm cực kì quan trọng trong toán học và trong tin học. Vì vậy nắm rõ được bản chất về mặt kiến thức, về mặt phương pháp cũng như tư duy là điều bất cứ ai trong chúng ta đều mong muốn hướng tới. Thêm vào đó, khá nhiều bạn trong chúng ta còn cho rằng, bản chất của phép quy nạp chính là phép đệ quy đòi hỏi phép quy nạp.

Về mặt định nghĩa, người ta cho rằng, quy nạp là kết luận đi từ trường hợp riêng đi tới trường hợp tổng quát. Nghĩa là, kết luận tổng quát dựa trên việc nghiên cứu các tính chất của nhiều sự kiện, nhiều thí nghiệm hay nhiều quan sát riêng lẻ. Nếu kết luận chung dựa vào nghiên cứu tất cả các sự kiện riêng (các đối tượng, các hình, các số, vv…) thì quy nạp được gọi là đầy đủ hay hoàn chỉnh. Nếu kết luận chung dựa vào nghiên cứu một phần của tâp hợp tất cả các sự kiện (các đối tượng) thì quy nạp được gọi là không đầy đủ hay không hoàn chỉnh.

Trong nhiều lĩnh vực khác nhau của Toán học ( số học, hình học, giải tích...) ta thường gặp những bài toán với yêu cầu chứng minh mệnh đề chứa biến P(n) là một mệnh đề đúng với mọi giá trị nguyên dương của biến n.

Ví d ụ 1:

Chứng minh rằng với mọi số nguyên dương n, ta luôn có:

G iải:

(1)

Ta thấy (1) đúng khi n=1. (2)

Ta sẽ chứng minh khẳng định sau:

"Với k là một số nguyên dương tùy ý, nếu (1) đúng với n=k thì nó cũng đúng với

n=k+1" (3). Thật vậy:

Nếu (1) đúng với n=k tức là:

Suy ra:

, tức là (1) đúng với n=k+1.

Từ (2) và (3) ta suy ra (1) đúng với mọi giá trị nguyên dương của n.

Một cách khái quát, để chứng minh mệnh đề chứa biến P(n) là một mệnh đề đúng

với mọi giá trị nguyên dương của n, ta thực hiện hai bước sau:

Bước1:( bước cơ sở hay bước mở đầu) Chứng minh P(n) đúng khi n=1.

Bước2:( bước quy nạp hay bước di truyền) Với k là một số nguyên dương, xuất phát từ giả thiết ( được gọi là giả thiết quy nạp) P(n) đúng với n=k, ta chứng minh P(n) cũng là mệnh đề đúng với n=k+1.

Ta có thể kết luận: [P(1) ∧ ∀n(P(n) → P(n 1))] → ∀nP(n).

Chú ý rằng khi chúng ta sử dụng quy nạp toán học để chứng minh, đầu tiên chúng ta chỉ ra rằng P(1) là đúng. Khi đó chúng biết rằng P(2) là đúng, bởi vì P(1) đã ngầm dẫn tới P(2). Hơn nữa, chúng ta cũng chỉ ra được P(3) là đúng vì P(2) đã ngầm dẫn tới P(3). Tiếp tục như vậy P(k) là đúng cho bất kỳ số nguyên dương k nào. Chú ý thêm rằng trong chứng minh quy nạp chúng ta không giả định là P(n) đúng với mọi số nguyên dương! Đó chỉ là việc giả định rằngnếuP(n)màđúngthìP(n+1)cũng đúng.

Một minh họa hình thức cho quy nập toán học có thể hình ảnh hóa bằng hiệu ứng đổ

của các quân domino.

Tạisaochứngminhquynạplàđúng?Kỹ thuật chứng minh quy nạp dựa trên cơ sở lập luận chính xác. Giả sử chúng ta đã có P(1) là đúng và mệnh đề P(n)→P(n+1) là đúng cho mọi số nguyên n. Để chỉ ra P(n) đúng cho mọi số nguyên dương, giả định có ít nhất một số P(n) là sai. Thì khi đó tập S gồm các số nguyên dương để P(n) sai là khác rỗng. Từ đó ta kết luận S có ít nhất 1 phần tử, trong các phần tử sai đó ta chọn một phần tử, chúng ta ký hiệu là k sao cho P(k) sai còn P(k-1) đúng (chúng ta luôn chọn được k như vậy nếu không thì sao? Sinh viên có thể chứng minh điều này? ). Rõ ràng rằng k khác 1, bởi vì P(1) là đúng (đã được kiểm tra). Bởi vì k dương và lớn hơn 1 nên k-1 nguyên dương. Hơn nữa k-1 nhỏ hơn k, và k-1 không nằm trong tập S nên P(k-1) đúng. Phép kéo theo P(k-1)→P(k) đúng, mà P(k-

1) đúng nên P(k) phải đúng. Vì vậy, điều này mâu thuẫn với sự lựa chọn của k. Như

vậy, P(n) đúng cho mọi số nguyên dương n.

M ột s ố ví d ụ về p h ư ơ n g ph á p c h ứ n g m i n h q u y n ạ p.

Vídụ2:CMR với , ta luôn có: (4) Giải: Bước 1: Dễ thấy (4) đúng với n=1.

Bước 2: Giả sử (4) đúng với , tức là:

Ta CM (4) cũng đúng với n=k+1, tức là:

Thật vậy, từ giả thiết quy nạp, ta có:

Vậy (4) đúng với

Tương tự, hãy CM:

Vídụ3:CMR với mọi số nguyên dương , ta luôn có:

(5)

Giải

Bước 1: Với n=3, dễ thấy (5) đúng

Bước 2: Giả sử (5) đúng khi , tức là:

ta sẽ CM nó cũng đúng với n=k+1, tức là: Thật vậy, từ giả thiết quy nạp, ta có:

Vậy (5) đúng với mọi số nguyên dương

Vídụ4.Chứng minh rằng với mọi số nguyên đồng (tiền Việt Nam) lớn hơn 6 có thể đổi ra tiền lẻ không dư bằng những đồng tiền gồm những tờ 2 đồng và 5 đồng (1 đồng ở đây bằng 1000 đồng trong thực tế).

Lờigiải.Đẳng thức sau đây nói lên với 7 đồng, 8 đồng thì gồm tờ 2 đồng và 5 đồng như thế nào:

7 = 5 + 2;

8 = 2 + 2 + 2 +2.

Nếu ta thêm vào hai vế của các đẳng thức trên tờ 2 đồng, thì

9 = 7 + 2;

10 = 8 + 2.

Tiếp tục thêm 2 đồng vào hai đẳng thức sau cùng, ta có

11 = 9 + 2;

12 = 10 +2. Ta còn tiếp tục được cho bất cứ số nguyên nào. Ta thấy rằng ở bước trước có hai đẳng thức và suy ra bước sau có hai đẳng thức. Như vậy với mọi số n nguyên đồng nào dù là số chẵn hoặc số lẻ khi n-2 cũng rơi vào một trong hai trường hợp trước đó đã đổi được ra hai loại tiền 2 đồng và 5 đồng. Suy ra nó cũng đổi thành các đồng 2 đồng và 5 năm. Như vậy, khẳng định của của mệnh đề là đúng.

Vídụ5.Tính tổng n số tự nhiên đầu tiên.

Lời giải. Kí hiệu P(n) là tổng phải tìm, nghĩa là P(n) = 1 + 2 + 3 + ... + n. Ta tính một số tổng tại những giá trị ban đầu:

N	1	2	3	4	5	6	7
P(n)	1	3	6	10	15	21		28

Ta thấy quy luật: Tích của hai số liên tiếp ở hàng trên bằng 2 lần số đầu tiên ở hàng dưới. Như 1.2 = 2.1, 2.3 = 2.3, 3.4 = 2.6, 4.5 = 2.10, 5.6

=2.15, 6.7 = 2. 21, ... Như vậy ta có thể dự đoán công thức phải tìm là

(1) Biểu thức trên được gọi là giả thiết quy nạp. Muốn chắc chắn công thức này đúng ta phải chứng minh bằng phương pháp quy nạp thông qua hai bước:

1. Bước cơ sở: Với n = 1 công thức (1) đúng như cách tính ở trên.

2. Bước quy nạp: Giả sử n = k, P(k) đúng, nghĩa là đã có

Ta phải chứng minh (1) cũng đúng cho n = k + 1.

Thật vậy,

Do đó công thức (1) cũng đúng với n = k +1, theo nguyên lí quy nạp toán học công thức (1) đúng với mọi mọi n > 0.

Cách c h ứ ng m i n h b ằng ph ư ơ ng pháp quy n ạp toán h ọ c c ần thi ế t th ứ c hiện hai b ư ớ c như phân tích ở ph ầ n t r ên. N h ư ng khó kh ă n c h ủ yếu l à t r ong b ư ớ c q uy n ạp toán học là khi m ệnh đề g i ả s ử đ ã đúng cho P(k) p h ải ch ứ ng m inh cho P(k + 1). T h ư ờ ng ng ư ờ i ta t ì m m ối l i ên hệ gi ữ a P(k) v à P(k + 1) đ ể s uy r a k ết quả phải ch ứ ng m inh.