Chương 1 Phương pháp quy nạp toán học Phương pháp quy nạp toán học là một công cụ rất có hiệu lực trong việc chứng minh nhiều bài toán thuộc các lĩnh vực khác nhau của toán học như: số học, đại số, hình học. và đặc biệt là các bài toán không mẫu mực. Đây là một phương pháp chứng minh toán học đặc biệt cho phép ta rút ra những quy luật tổng quát dựa trên cơ sở những trường hợp riêng. Quá trình quy nạp ngược với quá trình suy diễn.
Từ "tính chất" của một số cá thể suy ra "tính chất" của tập thể, nên không phải lúc nào cũng đúng. Nó chỉ đúng khi thỏa mãn nguyên lý quy nạp.1 Nguyên lý quy nạp Cho n0 là một số nguyên dương và P (n) là một mệnh đề có nghĩa với mọi số tự nhiên n ≥ n0. Nếu P (k) đúng từ đó suy ra được P (k + 1) cũng đúng với mọi số tự nhiên k ≥ n0 thì P (n) đúng với mọi số tự nhiên n ≥ n0 .2 Phương pháp chứng minh bằng quy nạp Giả sử khẳng định P (n) xác định ∀n ≥ n0. Để chứng minh P (n) đúng ∀n ≥ n0 bằng quy nạp, ta cần thực hiện 2 bước 1.1 Cơ sở quy nạp Kiểm tra sự đúng đắn của P (n) với n = n0 , nghĩa là xét P (n0 ) có đúng không.
4 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.2 Quy nạp Chứng minh rằng: Nếu với mỗi k ≥ n0 , P (k) là mệnh đề đúng, thì suy ra P (k + 1) cũng đúng. Nếu cả 2 bước trên đều thỏa mãn, thì theo nguyên lý quy nạp P (n) đúng với mọi n ≥ n0. Chú ý Trong quá trình quy nạp, nếu không thực hiện đầy đủ cả 2 bước: Cơ sở quy nạp và quy nạp thì có thể dẫn đến kết luận sai lầm. Một số ví dụ sau sẽ chứng tỏ điều này.
- Do bỏ qua bước cơ sở quy nạp, ta đưa ra kết luận không đúng: Mọi số tự nhiên đều bằng nhau! Bằng cách quy nạp như sau: Giả sử các số tự nhiên không vượt quá k + 1 đã bằng nhau. Khi đó ta có: k =k+1 Thêm vào mỗi vế của đẳng thức trên 1 đơn vị sẽ có: k+1=k+1+1=k+2 Cứ như vậy suy ra mọi số tự nhiên không nhỏ hơn k đều bằng nhau. Kết hợp với giả thiết quy nạp: Mọi số tự nhiên không vượt quá k đều bằng nhau, đi đến kết luận sai lầm: Tất cả các số tự nhiên đều bằng nhau! - Do bỏ qua bước quy nạp nên nhà toán học Pháp P.Fermat (1601 - n 1665) đã cho rằng số dạng 22 + 1 đều là số nguyên tố.Fermat xét 5 số đầu tiên: 0 Với n = 0 cho 22 + 1 = 21 + 1 = 3 là số nguyên tố. 1 Với n = 1 cho 22 + 1 = 22 + 1 = 5 là số nguyên tố.
2 Với n = 2 cho 22 + 1 = 24 + 1 = 17 là số nguyên tố. 3 Với n = 3 cho 22 + 1 = 28 + 1 = 257 là số nguyên tố. 4 Với n = 4 cho 22 + 1 = 216 + 1 = 65537 là số nguyên tố. Nhưng vào thế kỷ XVIII, L.Euler (1707 - 1783) đã phát hiện với n = 5 khẳng định trên không đúng, bởi vì: 5 22 + 1 = 4294967297 = 641.6700417 là hợp số.
5 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.3 Vận dụng phương pháp quy nạp để giải bài toán không mẫu mực Phương pháp quy nạp được sử dụng trong tính toán, trong chứng minh và suy luận dưới nhiều dạng khác nhau, nhưng trong phần này chỉ trình bày việc vận dụng phương pháp quy nạp để giải bài toán không mẫu mực. Hãy xác định tất cả các số nguyên dương k, sao cho d(n2 ) = kd(n), với n là số nguyên dương nào đó. Giả sử khi phân tích ra thừa số nguyên tố, số n có dạng: n = pa11 .(ar + 1) (∗) Do (2ai + 1)(1 ≤ i ≤ r) đều là các số lẻ nên k phải là các số lẻ. Ta sẽ chứng minh mệnh đề đảo lại rằng: "Với số lẻ k bất kỳ, ta có thể tìm được các số ai thỏa mãn (*) (tức là tìm được n)".
Dùng phương pháp quy nạp theo k. Với k = 1, mệnh đề đúng (n = 1, ai = 0) 2. Giả sử mệnh đề đúng với số k nào đó, ta chứng minh nó cũng đúng cho (2m. Lúc đó mệnh đề đúng cho mọi số lẻ vì mọi số lẻ l đều viết được dưới dạng: (2m .k − 1) 6 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com chia hết cho (2m − 1)k có nghĩa là: (2m .k − 1) chia hết cho k.
Vậy nếu ta chọn các ai như trên với k đã cho, thì mệnh đề trên đúng cho (2m. Ta có điều phải chứng minh! Bài toán 1. (USAMTS, 2000 - 2001, Cuộc thi tài năng toán học Mỹ) Hãy tìm số dư khi chia số 17761492! cho 2000. Trước hết ta chứng minh bổ đề: "Với mọi số nguyên dương n, ta có: 1376n ≡ 1376(mod 2000)" Dùng phương pháp quy nạp: 1.
Với n = 1, hiển nhiên có: 13761 ≡ 1376(mod 2000) Với n = 2, ta có: 13762 = 1893376 ≡ 1376(mod 2000) 2. Giả sử mệnh đề đúng với n = k(k ∈ N, k ≥ 1), tức là: 1376k ≡ 1376(mod 2000). Ta chứng minh bổ đề đúng với n = k + 1. Thật vậy, từ giả thiết quy nạp ta có: 1376k+1 ≡ 13762 (mod 2000), mà 13762 ≡ 1376(mod 2000), nên 1376k+1 ≡ 1376(mod 2000) Bổ đề được chứng minh! Quay lại bài toán, ta có: 17765 = 1376(mod 2000), nên 1492! 17761492! = (17765 ) 5 Vậy khi chia số 17761492! cho 2000 được số dư là 1376.
Hãy tìm chữ số tận cùng của số: An = 22 + 1 với mọi số nguyên n, n ≥ 2. Với n = 2, số A2 = 22 + 1 = 17, có chữ số tận cùng là 7. Giả sử với n = k, số Ak = 22 + 1 có chữ số tận cùng là 7. Ta sẽ chứng minh Ak+1 có chữ số tận cùng là 7.
Thật vậy, do Ak có chữ số tận cùng là 7, nên tồn tại số nguyên dương m để: Ak = 10m + 7, hay: k 22 + 1 = 10m + 7 7 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com k Tức là: 22 = 10m + 6.2 + 1 k 2 = (22 ) + 1 = (10m + 6)2 + 1 = 100m2 + 120m + 37 = 10(10m2 + 12m + 3) + 7 nên Ak+1 cũng có chữ số tận cùng là 7. n Vậy với mọi số nguyên n, n ≥ 2, thì An = 22 + 1 có chữ số tận cùng là 7. (Vô địch toán Canada, 1982) Cho a, b và c là những nghiệm của phương trình: x3 − x2 − x − 1 = 0 Chứng minh rằng số: b1982 − c1982 c1982 − a1982 a1982 − b1982 + + b−c c−a a−b là một số nguyên. n −cn n −an n −bn Đặt un = b b−c , vn = c c−a , wn = aa−b , với n nguyên, n ≥ 1.
Ta sẽ chứng minh: un + vn + wn nguyên với mọi n nguyên, n ≥ 1(∗). Trước hết ta thấy rằng: un+3 = un+3 + un+3 + un , ∀n, n 6= 1. Thật vậy, do b, c là nghiệm của phương trình x3 − x2 − x − 1 = 0 nên: b3 = b2 + b + 1, c3 = c3 + c + 1 Do đó: bn+3 − cn+3 un+3 = b−c b .c3 n 3 = b−c b (b + b + 1) − cn (c2 + c + 1) n 2 = b−c n+2 n+2 b −c bn+1 − cn+1 bn − cn = + + b−c b−c b−c = un+2 + un+1 + un 8 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Tương tự ta có: vn+3 = vn+2 + vn+1 + vn wn+3 = wn+2 + wn+1 + wn Tiếp theo, ta sẽ dùng phương pháp quy nạp để chứng minh khẳng định (*) 1. Với n = 1, ta có: u1 + v1 + w1 = 1 + 1 + 1 = 3 ∈ Z Với n = 2, ta có: b2 − c2 c2 − a2 a2 − b2 u2 + v2 + w2 = + + b−c c−a a−b −1 = 2(a + b + c) = 2(− ) = 2 ∈ Z 1 Với n = 3 ta có: b3 − c3 c3 − a3 a3 − b3 u2 + v2 + w2 = + + b−c c−a a−b 2 2 2 = 2(a + b + c ) + (bc + ca + ab) = 2(a + b + c)2 − 3(bc + ca + ab) −1 −1 = 2(− )2 − 3( ) = 5 ∈ Z 1 1 Vậy khẳng định đúng với n = 1, 2, 3.
Giả sử khẳng định đúng với n = k, k + 1, k + 2(k ≥ 1). Ta chứng minh khẳng định đúng với n = k + 3. Thật vậy, ta có: uk+3 + vk+3 + wk+3 = (uk+2 + uk+1 + uk ) + (vk+2 + vk+1 + vk ) + (wk+2 + wk+1 + wk ) (uk+2 + vk+2 + wk+2 ) + ((uk+1 + vk+1 + wk+1 ) + (uk + vk + wk ) Theo giả thiết quy nạp, cả ba số hạng của tổng trên đều nguyên nên (uk+3 + vk+3 + wk+3 ) cũng nguyên. Khẳng định được chứng minh.
Từ đó hiển nhiên tổng ở đề bài là số nguyên. (IMO 1973) Cho OP1 , OP2 , ., OP2n+1 là các vecto đơn vị trong mặt phẳng. Các điểm P1 , P2 , P2n+1 đều cùng nằm về 1 phía của đường thẳng qua O. Chứng minh rằng: −−→ −−→ −−−−→ |OP1 + OP2 +.
+ OP2n+1 | ≥ 1 Chứng minh. 9 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Với n = 1, mệnh đề hiển nhiên đúng do: −−→ |OP1 | = 1 ≥ 1 2. Giả sử mệnh đề đúng với n = k − 1(k ≥ 2), tức là với hệ vecto −−→ −−→ −−−−→ đơn vị: OP1 , OP2 , ., OP2k−1 cùng nằm về 1 phía của 1 đường thẳng qua O, ta đã có: −−→ −−→ −−−−→ |OP1 + OP2 +.
+ OP2k−1 | ≥ 1 Ta chứng minh mệnh đề đúng với n = k, tức là với hệ (2k + 1) vecto −−→ −−→ −−−−→ OP1 , OP2 , ., OP2k+1 thỏa mãn các điều kiện trên, ta cũng có: −−→ −−→ −−−−→ |OP1 + OP2 +. + OP2k+1 | ≥ 1 −−→ Thật vậy, do vai trò của OPi (1 ≤ i ≤ 2k + 1) như nhau nên ta có thể −−→ −−−→ −−−−→ sắp xếp lại sao cho OPi (1 ≤ i ≤ 2k − 1) nằm giữa OP2k và OP2k+1 Đặt: → − −−−→ −−−−→ u = OP2k + OP2k+1 → − −−→ −−→ −−−−→ v = OP + OP + .