Chuyên đề Phương pháp quy nạp toán học (Phần 2) - Bồi dưỡng HSG Toán 8

 CHUYÊN ĐỀ 7 : PHƯƠNG PHÁP QUY NẠP TOÁN HỌC
 I. KIẾN THỨC TRỌNG ĐIỂM
 1. Nguyên lý quy nạp toán học (PMI)
 Phương pháp quy nạp toán học thực sự có hiệu lực với lớp các bài toán chứng minh một mệnh đề phụ thuộc 
 vào số tự nhiên n N 
 Để chứng minh một mệnh đề Q n đúng với n p , ta thực hiện 2 bước theo thứ tự:
 Bước 1 : Kiểm tra mệnh đề đúng với n p
 Bước 2 : Giả sử mệnh đề đúng với n k p , ta phải chứng minh rằng mệnh đề đúng với n k 1
 1. Nguyên lý quy nạp toán học mạnh (PSMI)
 Nguyên lý quy nạp toán học mạnh (gọi tắt là nguyên lý quy nạp mạnh), kí hiệu là PSMI, viết tắt chữ cái đầu 
 của các từ tiếng Anh: Principle of Strong Mathermatics induction. Nội dung nguyên lý quy nạp mạnh như 
 sau:
 Giả sử mệnh đề M n theo các số tự nhiên n thỏa mãn:
 (1) M n0 đúng với số tự nhiên n0 nào đó
 (2) Với mỗi số tự nhiên n n0 , nếu M n0 , M n0 1 ,...., M n đúng thì M n 1 đúng 
 (3) Khi đó mệnh đề M n sẽ đúng với mọi số tự nhiên n n0
 *) Chú ý: 
 a) Như vậy, PSMI chỉ khác PMI ở bước quy nạp: ở PSMI, chúng ta giả sử rằng không chỉ M n đúng mà tất 
 cả các M j đúng với j n0 ,...,n thì M n 1 đúng. Tuy nhiên từ sự khác nhau này, trong một số bài 
 toán thì việc dùng PSMI sẽ tiện lợi hơn khi dùng PMI.
b) Phương pháp PSMI cũng thường dùng để chứng minh dạng đóng(closed form) đối với các phần tử của 
 một dãy xác định bởi quan hệ đệ quy. Có thể hiểu rằng dạng đóng các phần tử của một dãy số là biểu hiện 
 dưới dạng có thể tính được mà không cần biết các phần tử khác của dãy số. 
 II. Các dạng toán
 Dạng 1: Sử dụng phương pháp quy nạp chứng minh công thức
 Ví dụ 1: Chứng minh rằng với mọi số tự nhiên n 2 , ta có:
 an – bn a – b an–1 an – 2.b  a.bn 2 bn– 1 1 
 Lời giải
 Khi n 2 thì: VT 1 a2 b2 ; VP 1 a b a b a2 b2
 Vậy đẳng thức (1) đúng với n 2 k 1
Thậy vậy, cộng vào hai vế của (3.1) một lượng , ta được (3.2)
 3k 1
Vậy (3) đúng với n k 1, nên cũng đúng với mọi n N *
 n n 1 
Ví dụ 4: Chứng minh rằng với mọi số nguyên dương n , ta có: 1 2 3 .... n (4)
 2
 Lời giải
 1.2
Với n 1, ta có: 1 1 (đúng)
 2
Vậy (4) đúng với n 1
 k k 1 
Giả sử (4) đúng với n k 1, nghĩa là 1 2 3 ... k 
 2
 k 1 k 2 
Ta sẽ chứng minh (4) cũng đúng với n k 1, nghĩa là: 1 2 3 ... k k 1 
 2
Từ giả thiết quy nạp, ta có: 
 k k 1 k k 1 2 k 1 k 1 k 2 
VT 1 2 3 ... k k 1 k 1 VP (đpcm).
 2 2 2
Vậy (4) đúng với mọi n ¥ * .
Ví dụ 5: Chứng minh rằng với mọi số nguyên dương n , ta luôn có đẳng thức sau: 
 2 2n n 1 2n 1 
22 42 ... 2n (5)
 3
 Lời giải
 2 1 1 . 2 1 
Với n 1, ta có 22 4 , đúng. Vậy (5) đúng với n 1
 3
 2 2k k 1 2k 1 
Giả sử (5) đúng với n k 1, nghĩa là 22 42 ... 2k 
 3
Ta sẽ chứng minh (5) cũng đúng với n k 1, nghĩa là:
 2 2 k 1 k 2 2k 3 
22 42 ... 2 k 1 
 3
 2 2 2k k 1 2k 1 2
Từ giả thiết quy nạp ta có: VT 22 42 ... 2k 2 k 1 2 k 1 
 3 
 2
 2k k 1 2k 1 3 2 k 1 2 k 1 k 2k 1 6 k 1 
 3 3
 2 k 1 2k 2 7k 6 2 k 1 k 2 k 3 
 VP (đpcm).
 3 3
Vậy (5) đúng với mọi n ¥ * . m 1
 1 1
Theo bất đẳng thức Bernoulli ta có: 1 1 m 1 . 2
 m 1 m 1
 m 1 m 1
 m 2 1 m 2 
Vì vậy m 1 ! m 1 .m! 2 . , suy ra điều phải chứng minh.
 2 2 2 
 n
 1 
Ví dụ 2: Chứng minh rằng: 1 n,n N,n 2 (5)
 n 
 Lời giải
 3
 1 64
Khi n 3, bất đẳng thức (5) trở thành 1 3 (đúng)
 3 27
 k
 1 
Giả sử bát đẳng thức (5) đúng với n k nghĩa là: 1 k đúng.
 k 
 k 1
 1 
Ta chứng minh bất đẳng thức (5) đúng với n k 1, tức là: 1 k 1
 k 1 
 k 1 k k
 1 1 1 1 1 1 
Ta có: 1 1 1 1 . 1 k. 1 k 1
 k 1 k 1 k 1 k k k 
Vậy bất đẳng thức (5) đúng với n k 1 nên nó cũng đúng với mọi n.
Ví dụ 3: Cho x1, x2 ,...., xn là các số dương. Chứng minh rằng :
 x x x3 x x
 1 2 ... n 1 n 2,n 4 (6)
x2 xn x3 x1 x4 x2 xn xn 2 x1 xn 1
 Lời giải
 x x x x x x x x
Với n 4 , bất đẳng thức có dạng: 1 2 3 4 2 1 3 2 4 2 (đúng)
 x2 x4 x3 x1 x4 x2 x1 x3 x2 x4 x1 x3
 x x x x
Giả sử (6) đúng với n k . Tức là 1 1 ... k 1 k 2, k 4 (6.1) 
 x2 xk x3 x1 xk xk 2 x1 xk 1
Ta chứng minh (6) đúng với n k 1.
Do vai trò bình đẳng giữ các xi i 1,2,...,k 1 , nên không giảm tính tổng quát của bài toán ta có thể giả sử 
xk 1 min x1, x2 ,..., xn , tức là xk 1 0, xk 1 xk , xk 1 x1
 x1 x2 xk xk 1 x1 x2 xk
Do vậy ta có: Sk 1 ... ... (6.2)
 x2 xk 1 x3 x1 xk 1 xk 1 x1 xk x2 xk x3 x1 x1 xk 1
 x x x x x
Do: 1 1 ; k k ; k 1 0 (6.3)
 x2 xk 1 x2 xk xk 1 xk 1 x1 xk 1 x1 xk Dạng 3: Sử dụng phương pháp quy nạp vào bài toán chia hết
Ví dụ 1: Chứng minh rằng: n4 n2 12 với mọi số nguyên dương n .
 Lời giải
Gọi M n là mệnh đề cần chứng minh n4 n2 12,n ¥ *
Trước hết ta thấy mệnh đề đúng với 6 số nguyên dương đầu tiên
- Với n 1 thì 14 12 012
- Với n 2 thì 24 22 1212
- Với n 3 thì 34 32 7212
- Với n 4 thì 44 42 24012
- Với n 5 thì 54 52 60012
- Với n 6 thì 64 62 126012
Với n 6 , ta giả sử j4 j2 12 với mọi số nguyên j , 1 j n (nghĩa là các mệnh đề 
M 1 , M 2 ,..., M n đúng).
Ta phải chứng minh n 1 4 n 1 2 12 (tức là M n 1 đúng).
Do M n 5 đúng, nên n 5 4 n 5 2 12
Đặt k n 5, khi đó k 4 k 2 12 hay k 4 k 2 12b,b ¢
Ta có: n 1 4 n 1 2 k 6 4 k 6 2
 k 4 24k 3 216k 2 864k 1296 k 2 12k 36 
 k 4 k 2 24k 3 216k 2 852k 1296
 12b 24k 3 216k 2 852k 1296
 12 b 2k 3 18k 2 71k 105 
 12c với c b 2k 3 18k 2 71k 105 ¢
Theo PSMI thì n 1 4 n 1 2 12 với mọi số nguyên dương n .
Ví dụ 2: Chứng minh rằng với mọi n ¢ , ta có:
a) 2n 3n 5n 6 (1)
b) 16n 10n 125 (2)
 Lời giải
a) Với n 1 ta được 06 (đúng)
Giả sử (1) đúng với n k , tức là 2k 3k 5k 6 Dạng 4: Sử dụng phương pháp quy nạp chứng minh các bào toán hình học
 n n 3 
Ví dụ 1: Chứng minh rằng số đường chéo của đa giác lồi n cạnh n 4 là S 
 n 2
 Lời giải
 4 4 3 
Với n 4 , ta có số đường chéo của tứ giác lồi là S 2
 4 2
 k k 3 
Giả sử với n k 4 ta có số đường chéo của đa giác lồi k cạnh là S 
 k 2
 k 1 k 2 
Ta phải chứng minh đa giác lồi k 1 cạnh có đường chéo.
 2
Thật vậy, với đa giác lồi cạnh A1, A2 ,..., Ak , Ak 1 bất kì, ta có đa giác A1, A2 ,..., Ak là một đa giác lồi k cạnh 
 k k 3 
nên số đường chéo của nó là S . Khi đó các đường chéo của đa giác A , A ,..., A , A bao gồm 
 k 2 1 2 k k 1
các đường chéo của đa giác A1, A2 ,..., Ak , các đường Ax Ak 1 x 2.k 1 và A1 Ak . Do đó số đường chéo của 
 k k 3 k 1 k 2 
A , A ,..., A , A là: S S k 2 1 k 1 
 1 2 k k 1 k 1 k 2 2
 n n 3 
Vậy số đường chéo của đa giác lồi n cạnh n 4 bất kì là S .
 n 2
 0
Ví dụ 2: Chứng minh rằng tổng các góc trong của đa giác lồi n cạnh n 3 là Sn n 2 .180
 Lời giải
 0 0
Với n 3, ta có tổng các góc trong của tam giác là S3 3 2 .180 180
 0
Giả sử với n k 3 ta có tổng các góc trong của đa giác lồi k cạnh là Sk k 2 .180 .
Ta phải chứng minh đa giác lồi k 1 cạnh có tổng các góc trong bằng k 1 .1800 .
Thật vậy, với đa giác lồi k 1 cạnh A1 A2 A3...Ak Ak 1 bất kì, ta có đa giác A1 A2 A3...Ak là một đa giác lồi k 
 0
cạnh nên tổng các góc trong của nó là Sk k 2 .180 . Khi đó tổng các góc trong của đa giác 
A1 A2 A3...Ak Ak 1 bằng tổng các góc trong của đa giác A1 A2 A3...Ak và tam giác A1 Ak Ak 1 . Do đó 
 0 0 0
Sk 1 k 2 .180 180 k 1 .180
 0
Vậy tổng các góc trong của đa giác lồi n cạnh n 3 bất kì là Sn n 2 .180 .
Ví dụ 3: Chứng minh rằng nếu ABC vuông tại A , có số đo các cạnh là a,b,c thì với mọi số tự nhiên 
n 2 ta luôn có bất đẳng thức bn cn an
 Lời giải
Với n 2 , ta có bất đẳng thức đúng vì theo định lí Pythagore thì b2 c2 a2 .