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

 PHƯƠNG PHÁP QUY NẠP TOÁN HỌC 
1 Cơ sở lí luận: 
 1.1. Khái quát chung về tập hợp số tự nhiên ¥ 
Các số 0, 1, 2, 3,... là các số tự nhiên. Tập hợp số tự nhiên kí hiệu là 
 ¥ 0;1;2;3;... 
Các số 0, 1, 2, 3, ...là các phần tử của tập hợp 
Tập hợp các số tự nhiên khác 0 được kí hiệu là ¥ * 
 ¥ * 1;2;3;... 
Trong hai số tự nhiên khác nhau, có một số nhỏ hơn số kia. 
Mỗi số tự nhiên có một số liền sau duy nhất. 
Hai số tự nhiên liên tiếp thì hơn kém nhau một đơn vị 
Số 0 là số tự nhiên nhỏ nhất. không có số tự nhiên lớn nhất 
Số 1 là số tự nhiên khác không nhỏ nhất 
Tập hợp các số tự nhiên có vô số phần tử 
 1.2 Nguyên lí qui nạp 
 Định lí 2.1 
 Cho n0 là một số nguyên dương và P(n) là mệnh đề có nghĩa với một số tự 
nhiên nn 0 . Nếu 
a) P( ) là đúng 
b) Nếu P(k) đúng thì P(k+1) cũng đúng với mỗi số tự nhiên kn 0 , khi đó mệnh 
đề P(n) đúng với mọi số tự nhiên 
 1.3 Giai đoạn qui nạp và giả thiết qui nạp 
 Để hiểu cách áp dụng phương pháp qui nạp cho đầy đủ, ta xem xét một số ví 
dụ sau đây như một phép « suy luận có lí » mà G. Polya đã đề cập. 
 Ví dụ 1 : Chứng minh rằng với n ¥ * ta có 
 1.2 2.5 3.8 ... n (3 n 1) n2 ( n 1) (2.1) 
Giải : 
 - 1 - 32
Đặt An n 35 n n 
Bước 1 :Với n = 1, ta có A1 93M . 
 32
Bước 2 : Giả sử với nk 1 ta đã có Ak k 3 k 5 kM 3 
Ta phải chứng minh Ak 1M3 
Thật vậy, ta có 
 3 2 3 2 2
 Ak 1 ( k 1)3( k 1)5( k 1) k 3 k 3 k 13 k 6 k 35 k 5 
 (k3 3 k 2 5 k ) 3 k 2 9 k 9. 
Theo giả thiết qui nạp thì , do đó 
Vậy chia hết cho 3 với mọi n ¥ * 
 Ví dụ 4 : Cho trước một số tự nhiên n. Hãy tìm tổng các số tự nhiên 1, 2, ..., n 
 Giải : 
Ta kí hiệu Sn là tổng phải tìm, nghĩa là Snn 1 2 ... (2.4) 
Ta hi vọng tìm ra công thức ngắn gọn để tính tổng trên, công thức đó giúp ta 
tính nhanh, gọn hơn là phải thực hiện lần lượt các phép cộng trong tổng. Ta 
minh hoạ quá trình áp dụng nguyên lí qui nạp vào tính tổng này. 
 Ta tính tổng từ đẳng thức (2.4) với một vài số tự nhiên liên tiếp, chẳng hạn 
bắt đầu bằng 1. Những kết quả tính toán các trường hợp riêng được xếp vào 
bảng 
 n 1 2 3 4 5 6 
 1 3 6 10 15 21 
 Mục đích của ta là tìm được qui luật chung, với bảng trên ta dễ thấy qui luật : 
Tích của hai số tự nhiên ở hàng trên bằng hai lần số đầu tiên tương ứng ở hàng 
dưới.Thật vậy, 1.2=2.1 ; 2.3=2.3 ; 3.4=2.6 ;4.5=2.10 ; 5.6=2.15 .Như vậy giai 
đoạn qui nạp của chúng ta đã thành công với các trường hợp n= 1, 2, 3, 4, 5, 6 
 - 3 - Snn 1 3 5 ... (2 1) 
 Để xây dựng giả thiết qui nạp ta tính tổng của một số giá trị được liệt kê trong 
bảng sau 
 n 1 2 3 4 5 6 
 1 4 9 16 25 36 
 Bây giờ phụ thuộc vào sự quan sát của ta và kinh nghiệm trên kết quả riêng để 
dự đoán mệnh đề tổng quát chung. Dễ thấy các số ở hàng đều là số chính 
phương : 
 2 2 2 2 2 2
 SSSSSS1 1, 2 2, 3 3, 4 4, 5 5, 6 6
 2
 Như vậy ta có thể đưa ra giả thiết chung là : Snn (2.5) 
 Bước cơ sở : Với n = 1, tổng chỉ có một số hạng =1 ; biểu thức n2 1 với 
 Sn
 n = 1, như vậy (2.5) đúng. 
 2
 Bước qui nạp : Giả sử (2.5) đúng với n = k, tức là Skk . Ta sẽ chứng minh 
 2
(2.4) đúng với n = k+1, nghĩa là Skk 1 ( 1) 
Thật vậy, theo giả thiết qui nạp ta có 
 22
 Skk 1 S (2 k 1) k (2 k 1)( k 1). 
Như vậy bài toán đã giải xong. 
 1.4 Phương pháp qui nạp toán học trên ¥ * 
 Để chứng minh những mệnh đề liên quan đến số tự nhiên n ¥ * là đúng với 
mọi n mà không thể thử trực tiếp được thì có thể làm như sau : 
 Bước 1 : Kiểm tra rằng mệnh đề đúng với n = 1 
 Bước 2 : Giả thiết mệnh đề đúng với một số tự nhiên bất kì nk 1(gọi 
 là giả thiết qui nạp), chứng minh rằng nó cũng đúng với nk 1 
 Khẳng định mệnh đề đúng với mọi số tự nhiên n ¥ * 
*) Chú ý : 
 - 5 - Lời giải. Giả thiết bất đẳng thức (1.8) đúng với n = k,với k là một số tự nhiên 
nào đó, nghĩa là ta có 
 2k 2k 1 (2.4) 
Ta sẽ chứng minh bất đẳng thức (1.8) đúng với nk 1 
 2k 1 2(k 1) 1 (2.5) 
 Thật vậy, 22k (*) với mọi . Cộng vế với vế hai bất đẳng thức (2.4) và 
(*) ta nhận được 
 2kk 2 2k 1 2 
Nghĩa là 
Bài toán đã giải xong. 
 Tuy nhiên ví dụ này cũng mắc sai lầm như ví dụ trước không qua bước cơ sở 
Ví dụ 3 : Chứng minh rằng những giá trị của hàm số f( n ) n2 n 41với 
n = 0, 1, 2, ... là những số nguyên tố. 
 Lời giải. Ta tính 
 f 0 1, f 1 41, f 2 43, f 3 47, f 4 53, f 5 61,
 f 6 71, f 7 83, f 8 97, f 9 113
Ta có thể tính toán tiếp tục giá trị của f(n) cho tới n = 40, tất cả giá trị này đều 
là số nguyên tố. Nhưng với n = 41 ta có f 41 412 kết quả f 41 không phải 
là số nguyên tố, nên kết luận của bài toán là không đúng. như vậy ta thấy một 
mệnh đề có thể đúng với 40 trường hợp nói riêng nhưng không đúng với mọi 
trường hợp nói chung. 
 Còn rất nhiều khẳng định sai nếu vận dụng qui nạp theo cách như các ví dụ 
trên. 
 2. 2 Chưa biết vận dụng giả thiết qui nạp 
- Một thực trạng nữa cho thấy học sinh rất lúng túng trong việc vận dụng giả 
 n ¥ *
thiết qui nạp 
 Ví dụ 4 : 
 - 7 - - Nắm chắc và thực hiện bắt buộc trình tự hai bước của phương pháp qui 
nạp 
 - Ở bước 2 phải đặt ra được bài toán, trong đó : 
Giả thiết (qui nạp) là mệnh đề đúng nk và kết luận là mệnh đề đúng 
 nk 1 ; cần làm rõ được sự hơn kém giữa vế trái của đẳng thức giả thiết và 
vế trái của đẳng thức kết luận 
 - Hoàn thành xong hai bước phải nêu kết luận cuối cùng. 
Bài toán 1 : Chứng minh rằng với ta có 
 nn 31 
 2 5 8 ... 3n 1 (1) 
 2
Lời giải : 
Bước 1 : Với n = 1, ta có VT = 2, VP = 2. Vậy đẳng thức đúng với n = 1 
Bước 2 : Đặt vế trái bằng Sn 
Giả sử đẳng thức (1) đúng với nk 1, nghĩa là : 
 kk 31 
 S 2 5 8 ... 3k 1 (giả thiết qui nạp) 
 k 2
Ta phải chứng minh (1) cũng đúng với nk 1, nghĩa là 
 (kk 1) 3( 1) 1
 S 2 5 8 ... 3kk 1  3( 1) 1 
 k 1 2
Thật vậy, từ giả thiết qui nạp ta có : 
 k(3 k 1) 3 k2 k 6 k 4
 S S 3 k 2 3 k 2 
 kk 1 22 
 3(k2 2 k 1) k 1 (kk 1) 3( 1) 1
 (đpcm). 
 22
Bài toán 2 : Chứng minh rằng với n ¥ * ta có 
 1 1 1 1 2n 1 *
 ... n ¥ (2) 
 2 4 8 2nn 2
Lời giải : 
 - 9 - k(4 k2 1) (2 k 1)[ k (2 k 1) 3(2 k 1)]
 (2k 1)2 
 33
 (k 1)(2 k 3)(2 k 1) (kk 1)[4( 1)2 1]
 3 nk 3
Vnkậy hệ 1thức (3) đã được chứng minh. 
 3.2 Vận dụng qui nạp chứng minh bất đẳng thức 
 *) Chú ý: 
 - Nắm chắc và thực hiện bắt buộc trình tự hai bước của phương pháp qui 
nạp 
 - Ở bước 2 phải đặt ra được bài toán, trong đó : 
Giả thiết (qui nạp) là mệnh đề đúng và kết luận là mệnh đề đúng 
 ; cần vận dụng tốt tính chất của bất đẳng thức. 
 - Hoàn thành xong hai bước phải nêu kết luận cuối cùng. 
Bài toán 4 : Chứng minh rằng với mọi số tự nhiên n 3 ta có 
 3n nn2 4 5 (4) 
Lời giải : 
 Bước 1 :Với n = 3, vế trái bằng 27, vế phải bằng 26. Bất đẳng thức (4) đúng. 
Bước 2 : Giả sử bất đẳng thức đúng với nk 3, tức là 
 3k kk2 4 5 (4’) 
Ta phải chứng minh nó cũng đúng với nk 1, tức là 
 3k 12 (kk 1) 4( 1) 5 
Thật vậy, nhân hai vế của bất đẳng thức (4’) với 3 ta có 
 3k 1 3k 2 12 k 15( k 1) 2 4( k 1)52 k 2 6 k 5 
Vì 2kk2 6 5 0 nên 
Bất đẳng thức (4) đã được chứng minh 
Bài toán 5 : Chứng minh rằng với mọi số tự nhiên n 2 ta có 
 - 11 - Giả thiết (qui nạp) là mệnh đề đúng và kết luận là mệnh đề đúng 
 ; cần vận dụng tốt hằng đẳng thức đáng nhớ, tính chất chia hết của 
một tổng. 
 nk 1
 - Hoàn thành xong hai bước phải nêu kếtnk luận cuối cùng. 
Bnkài toán1 7 : Chứng minh rằng với ta có 
 nn3 11 chia hết cho 6 
Lời giải : 
 3
Đặt An n11 n 
 3
Bước 1 :Với n = 1, ta có A1 1 11 12 6. 
 3
Bước 2 : Giả sử với ta đã có Ak k11 k 6 
 3
Ta phải chứng minh Ak 1 6, tức là Ak 1 ( k 1) 11( k 1) 6 
Thật vậy, ta có 
 3 3 2
 Ak 1 ( k 1) 11( k 1) k 3 k 1 11 k 11 
 3 2 2
 (k 11 k ) 3( k k 4) Ak 3( k k 4) 
 2
Vì Ak 6 và k k 4 k ( k 1) 4 là số chẵn nên 
 3*
Vậy An n 11 nM¥ 6,  n 
Bài toán 8 : Chứng minh rằng với mọi n ¥ * ta có 
 nn7 chia hết cho 7 
Lời giải : 
 7
Đặt An n n 
Bước 1 :Với n = 1, ta có A1 07M . 
 7
Bước 2 : Giả sử với ta đã có Ak k kM7 
 7
Ta phải chứng minh Ak 1M7 , tức là A ( k 1) ( k 1) 
 k 1 n ¥ *
Thật vậy, áp dụng công thức nhị thức Niu-tơn ta có 
 7 7 6 5 4 3 2
 Akk 1 ( 1) ( kkkkkkkkk 1) 7 21 35 35 21 7 1 1 
 - 13 - 11
 S 
 1 1.3 3
 1 1 2
 S 
 nk 1 2 3 3.5 5
 2 1 3
 S 
nk 1 3 5 5.7 7
 3 1 4
 S 
 4 7 7.9 9
b) Từ kết quả câu a) ta dự đoán 
 n
 s . 
 n 21n 
Ta sẽ chứng minh công thức (7) bằng phương pháp qui nạp 
Bước 1 : với n = 1, theo a) thì (7) đúng 
Bước 2 : Giả sử với ta đã có 
 k
s . 
 k 21k 
Ta phải chứng minh nó cũng đúng với n = k+1 
Thật vậy, từ giả thiết qui nạp ta có 
 11
SSS 
 k 1 k2(k 1) 1 2( k 1) 1 k (2 k 1)(2 k 3)
 k1 k (2 k 3) 1
 2k 1 (2 k 1)(2 k 3) (2 k 1)(2 k 3)
 2k2 31 k (1)(21) k k k 1
 (2k 1)(2 k 3) (2 k 1)(2 k 3) 2( k 1) 1
tức là (7) cũng đúng với . Vậy công thức (7) đã được chứng minh. 
 nn( 3)
Bài toán 11 : Chứng minh số đường chéo của đa giác lồi n cạnh là 
 2
 Lời giải : 
 4(4 3)
 Với n = 4 số đường chéo của tứ giác là 2 
 2
 - 15 -