Sáu phương pháp giải các bài toán phổ thông

  • Số trang: 83 |
  • Loại file: PDF |
  • Lượt xem: 43 |
  • Lượt tải: 0
nhattuvisu

Đã đăng 26946 tài liệu

Mô tả:

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ————————– VŨ THỊ HIỀN SÁU PHƯƠNG PHÁP GIẢI CÁC BÀI TOÁN PHỔ THÔNG LUẬN VĂN THẠC SĨ KHOA HỌC Hà Nội - 2015 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ————————– VŨ THỊ HIỀN SÁU PHƯƠNG PHÁP GIẢI CÁC BÀI TOÁN PHỔ THÔNG Chuyên ngành: Phương pháp toán sơ cấp Mã số : 60460113 LUẬN VĂN THẠC SĨ KHOA HỌC Người hướng dẫn khoa học: GS.TS. Đặng Huy Ruận Hà Nội - 2015 Mục lục Mở đầu 1 1 Phương pháp quy nạp 1.1 Nguyên lý quy nạp . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Phương pháp chứng minh bằng quy nạp . . . . . . . . . . . . . . 1.2.1 Cơ sở quy nạp . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.2 Quy nạp . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.3 Vận dụng phương pháp quy nạp để giải một số bài toán . . . . . 2 2 2 3 3 4 . . . . 17 17 18 19 19 2 Phương pháp chứng minh phản chứng 2.1 Cơ sở lý thuyết . . . . . . . . . . . . . . . . . . . 2.2 Nội dung của phương pháp phản chứng . . . . . 2.3 Trình bày lời giải của phương pháp phản chứng . 2.4 Một số ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Phương pháp suy luận trực tiếp 28 3.1 Vài nét về phương pháp suy luận trực tiếp . . . . . . . . . . . . . . 28 3.2 Các ví dụ về vận dụng phương pháp suy luận trực tiếp . . . . . . 29 4 Phương pháp đồ thị 4.1 Một số khái niệm và kết quả cơ bản của lí thuyết đồ thị . . . . . 4.2 Phương pháp đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.1 Xây dựng đồ thị mô tả các quan hệ . . . . . . . . . . . . 4.2.2 Dựa vào các kết quả của lý thuyết đồ thị hoặc lý luận trực tiếp suy ra đáp án của bài toán D . . . . . . . . . . . . . 4.3 Một số ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 . 35 . 36 . 37 . 37 . 37 5 Phương pháp bảng 53 5.1 Giới thiệu về phương pháp bảng . . . . . . . . . . . . . . . . . . . . 53 i MỤC LỤC 5.2 Một số ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . . . . 53 6 Phương pháp sơ đồ 6.1 Các bước thực hiện phương pháp sơ đồ . . . . . . . . . . . . . . 6.1.1 Thiết lập sơ đồ . . . . . . . . . . . . . . . . . . . . . . . . 6.1.2 Dựa vào cấu trúc của sơ đồ mô tả quan hệ và điều kiện đã cho trong bài toán mà suy ra đáp án . . . . . . . . . . 6.2 Một số ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii 67 . 67 . 67 . . . . 67 67 77 79 Mở đầu Toán phổ thông chẳng những nhiều về số lượng, còn phong phú về chủng loại. Mỗi chủng loại đòi hỏi một phương pháp giải thích hợp. Bởi vậy có nhiều phương pháp giải toán phổ thông. Với khối lượng có hạn, luận văn chỉ xin phép trình bày sáu trong những phương pháp thường dùng nhất. Luận văn gồm phần mở đầu và sáu chương: Chương I trình bày về phương pháp quy nạp, Chương II trình bày về phương pháp phản chứng, Chương III trình bày về phương pháp suy luận trực tiếp, Chương IV trình bày về phương pháp đồ thị, Chương V trình bày về phương pháp bảng, Chương V I trình bày về phương pháp sơ đồ. Mỗi phương pháp đều có phần tóm tắt cơ sở lý thuyết và phần vận dụng phương pháp để giải bài tập. Luận văn được hoàn thành dưới sự hướng dẫn tận tình của thầy giáo GS. TS Đặng Huy Ruận. Em xin bày tỏ lòng kính trọng và biết ơn sâu sắc đến Thầy. Em xin trân trọng cảm ơn ban lãnh đạo khoa Toán - Cơ - Tin học, khoa Sau Đại học, Trường Đại học Khoa học tự nhiên, Đại học Quốc Gia Hà Nội, các Thầy, Cô giáo đã trang bị kiến thức, tạo điều kiện cho chúng em trong thời gian học tập tại đây. Tôi cũng xin gửi lời cảm ơn đến các Đồng nghiệp tại trường Phổ Thông Hồng Đức - Hà Nội, những người đã động viên giúp đỡ tôi rất nhiều trong quá trình hoàn thành luận văn này. Luận văn khó tránh khỏi hạn chế và sơ xuất. Rất mong được sự chỉ bảo của Quý thầy cô và Quý bạn đọc để luận văn được hoàn thiện hơn. Tôi xin chân thành cảm ơn! 1 Chương 1 Phương pháp quy nạp Phương pháp quy nạp có vai trò vô cùng quan trọng trong toán học, khoa học và cuộc sống. Đối với nhiều bài toán trong chương trình toán phổ thông là những bài toán logic, tức những bài toán không mẫu mực phương pháp quy nạp cho ta nhiều cách giải hữu hiệu. Suy diễn là quá trình từ "tính chất" của tập thể suy ra tính chất của cá thể, nên luôn luôn đúng, còn quá trình ngược lại, tức quá trình quy nạp: đi từ "tính chất" của một số các thể suy ra "tính chất" của tập thể thì không phải lúc nào cũng đúng, mà quá trình này chỉ đúng khi nó thỏa mãn một số điều kiện nào đó, tức thỏa mãn nguyên lý quy nạp. 1.1 Nguyên lý quy nạp Nếu khẳng định S(n) thỏa mãn hai điều kiện sau: a) Đúng với n = k0 (số tự nhiên nhỏ nhất mà S(n) xác định). b) Từ tính đúng đắn của S(n) đến n = t (hoặc đối với mọi giá trị của n (k0 ≤ n ≤ t)) (t ≥ k0 ), ta cần chứng minh tính đúng đắn của S(n) đối với n = t + 1, thì khiØS(n) đúng với mọi n ≥ k0 . 1.2 Phương pháp chứng minh bằng quy nạp Giả sử khẳng định S(n) xác định với mọi n ≥ t0 . Để chứng minh S(n) đúng ∀n ≥ t0 bằng quy nạp ta cần thực hiện theo hai bước sau: 2 Chương 1. Phương pháp quy nạp 1.2.1 Cơ sở quy nạp Thực hiện bước này tức là ta thử xem sự đúng đắn của S(n) với n = t0 nghĩa là xét S(t0 ) có đúng hay không? 1.2.2 Quy nạp Giả sử khẳng định S(n) đã đúng đến n = t (hoặc đối với mọi n (t0 ≤ n ≤ t)) (t ≥ t0 ). Trên cơ sở giả thiết này ta chứng minh tính đúng đắn của S(n) đối với n = t + 1, tức S(t + 1) đúng. Nếu cả ba bước trên thỏa mãn, thì theo nguyên lý quy nạp S(n) đúng với ∀n ≥ t0 . Chú ý: Trong quá trình quy nạp nếu không thực hiện đầy đủ cả ba bước: Cơ sở quy nạp, giả thiết quy nạp và chứng minh quy nạp, thì có thể dẫn đến kết quả sai lầm, chẳng hạn: - Do bỏ 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 một đơn vị ta 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 khâu quy nạp nên nhà toán học Pháp P.Fermat (1601-1665) đã n cho rằng các số dạng 22 + 1 đều là số nguyên tố. P.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 n = 1 cho 22 + 1 = 22 + 1 = 5 là số nguyên tố. n = 2 cho 22 + 1 = 24 + 1 = 17 là số nguyên tố. n = 3 cho 22 + 1 = 28 + 1 = 257 là số nguyên tố. n = 4 cho 22 + 1 = 216 + 1 = 65537 là số nguyên tố. 2 3 4 3 Chương 1. Phương pháp quy nạp Nhưng vào thế kỷ 18 Euler đã 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ố. 1.2.3 Vận dụng phương pháp quy nạp để giải một số bài toán Phương pháp quy nạp được sử dụng trong tính toán, trong chứng minh và trong 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 các bài toán logic, tức các bài toán "không mẫu mực". Ví dụ 1.2.1. Chứng minh rằng: Nếu trong túi có một số tiền nguyên (nghìn) không ít hơn 8000đ, thì luôn luôn có thể mua vé sổ số loại 5000đ và 3000đ. Lời giải: Ta sẽ giải quyết bài toán này bằng phương pháp quy nạp. 1) Cơ sở quy nạp. Nếu trong túi có số tiền ít nhất, tức 8000đ, thì ta mua một vé sổ số loại 5000đ và một vé sổ số loại 3000đ. Khi đó 1 × 5000đ + 1 × 3000đ = 8000đ và ta đã tiêu được hết số tiền có trong túi. 2) Quy nạp. Giả sử với k(k ≥ 8000) nghìn đồng ta đã tiêu hết bằng cách mua các vé sổ số loại 5000đ và 3000đ. Nếu có thêm 1000đ nữa ta cũng có thể mua được bằng cách sau đây: a) Nếu trong các vé sổ số đã mua có ít nhất ba vé loại 3000đ, thì ta trả lại ba vé loại 3000đ, đưa thêm 1000đ và lấy về hai vé loại 5000đ. Khi đó 3 × 3000đ + 1000đ = 2 × 5000đ. b) Nếu trong các vé sổ số đã mua có không quá hai vé loại 3000đ, thì phải có ít nhất một vé loại 5000đ. Bởi vì trong túi không ít hơn 8000đ, mà đã tiêu hết. Khi đó đem trả lại một vé loại 5000đ, đưa thêm 1000đ và lấy về hai vé loại 3000đ, ta có 1 × 5000đ + 1000đ = 2 × 3000đ Như vậy trong mọi trường hợp từ kết quả tiêu k nghìn đầu tiên đã suy ra được cách tiêu nghìn thứ k + 1, nên bài toán đã được giải quyết xong. 4 Chương 1. Phương pháp quy nạp Ví dụ 1.2.2. Em An cầm một tờ giấy và lấy kéo cắt thành 7 mảnh. Sau đó nhặt một trong những mảnh giấy đã cắt và lại cắt thành 7 mảnh. Và em An cứ tiếp tục cắt giấy như vậy. Sau một hồi em An thu tất cả các mẩu giấy đã cắt ra và đếm được 122 mảnh. Liệu em An đếm đúng hay sai? Lời giải: 1) Mỗi lần cắt mảnh giấy thành 7 mảnh, tức là đã tạo ra thêm 6 mảnh giấy, nên công thức tính số mảnh giấy sau n bước thực hiện một mảnh giấy thành 7 mảnh có dạng: S(n) = 6n + 1. 2) Tính đúng đắn của công thức S(n) được khẳng định bằng quy nạp theo n. 10 ) Cơ sở quy nạp. Với n = 1, em An cắt mảnh giấy có trong tay thành 7 mảnh, nên có S(1) = 6.1 + 1 = 6 + 1 = 7 20 ) Quy nạp. Giả sử sau k bước em An đã nhận được số mảnh giấy là S(k) = 6k + 1 Sang bước k + 1 em An lấy một trong những mảnh giấy nhận được trong k bước trước và cắt thành 7 mảnh, tức em An đã lấy đi một trong S(k) mảnh và thay vào đó 7 mảnh được cắt ra nên S(k + 1) = S(k) − 1 + 7 = 6k + 1 − 1 + 7 = 6k + 7 = 6k + 6 + 1 = 6(k + 1) + 1 Vậy số mảnh giấy em An nhận được sau n bước cắt giấy là S(n). 3) Do S(n) = 6n + 1 ≡ 1 (mod 6), nhưng 122 = 6.20 + 2 ≡ 2 (mod 6), nên em An đếm không đúng.  Ví dụ 1.2.3. (Chứng minh tính chất bằng quy nạp). Cho x + x1 , x 6= 0 là một số nguyên. Chứng minh rằng với mọi số nguyên dương n, số T (n, x) = xn + 1 xn cũng là số nguyên. Lời giải: Khẳng định được chứng minh bằng quy nạp. 1) Cơ sở quy nạp. Với n = 1 có T (1, x) = x + x1 là số nguyên, theo giả thiết. 2) Quy nạp. Giả sử khẳng định đúng với mọi số nguyên k(n ≥ k ≥ 1) nghĩa là T (k, x) = xk + 5 1 xk Chương 1. Phương pháp quy nạp là số nguyên. Với n = k + 1 số T (k + 1, x) = xk+1 +  = x+ 1 x 1 k+1 x  = xk + 1 xk   − xk−1 + 1 xk−1  1 theo giả thiết quy nạp, các số x + x1 , xk−1 + xk−1 và xk + x1k đều nguyên, nên T (k + 1, x) là số nguyên và khẳng định đúng với mọi số nguyên dương n.  Ví dụ 1.2.4. Chứng minh rằng mọi số nguyên lớn hơn 1 đều có thể viết dưới dạng tích của các thừa số nguyên tố. Lời giải: Ta chứng minh khẳng định bằng quy nạp theo n. 1. Cơ sở quy nạp. Với n = 2, ta có 2 = 2, Với n = 3, ta có 3 = 3, n = 4, ta có 4 = 2 × 2 Vậy khẳng định đúng với n = 2, 3, 4. 2. Quy nạp. Giả sử với mọi số nguyên n đều phân tích được thành tích của các thừa số nguyên tố. Ta chứng minh n + 1 cũng phân tích được thành tích của các thừa số nguyên tố. Thật vậy • Nếu n + 1 là số nguyên tố thì nó bằng tích của chính n + 1. • Nếu n + 1 là hợp số thì n + 1 = a.b với 2 ≤ a, b < n. Theo giả thiết quy nạp, thì a, b đều phân tích được thành tích các thừa số nguyên tố. Suy ra, n + 1 cũng phân tích được thành tích các thừa số nguyên tố. Theo nguyên lý quy nạp, mọi số nguyên n > 1 đều phân tích được thành tích các thừa số nguyên tố.  Ví dụ 1.2.5. (Chứng minh tính chia hết bằng quyh nạp). Chứng minh rằng với i  n n n . mọi số nguyên dương n số 23 + 1 chia hết cho 3n+1 23 + 1 ..3n+1 và số 23 + 1 h n i  . không chia hết cho 3n+2 23 + 1 6 ..3n+2 . Lời giải: Bài toán được giải quyết bằng quy nạp. Kí hiệu 23 + 1 = An . 1) Cơ sở quy nạp. 1 . . Với n = 1 ta có A1 = 23 + 1 = 23 + 1 = 8 + 1 = 9, nên A1 ..32 và A1 6 ..33 . 2 . . Với n = 2 ta có A2 = 23 + 1 = 513, nên A2 ..33 và A2 6 ..34 . n 6 Chương 1. Phương pháp quy nạp . 2) Quy nạp. Giả sử khẳng định đã đúng với n = k ≥ 2, nghĩa là Ak ..3k+1 và . Ak 6 ..3k+2 . . Vì Ak ..3k+1 , nên (Ak = M.3k+1 ∃M ∈ N . và M 6 ..3) (1.1) Xét n = k + 1 k+1 Ak+1 = 23 =3 k+1 k + 1 = 23 .M.  2 3k .3  k + 1 = 23 +1 h 2 − 3.2 . 3k k = 3k+1 .M. 32k+2 .M 2 − 3.23 3 i   k + 1 = 23 + 1 =3 k+1 .M. h 3   k+1 k 23 .M h 2 2 − 23 + 1 − 3.2 k = 3k+2 .M. 32k+1 .M 2 − 23 k i 3k  i . 10 ) Khi đó Ak+1 ..3k+2 , nên với mọi số nguyên dương n đều có 23 + 1..3n+1 . n . 20 ) Ak+1 6 ..3k+3 . . a) Vì M 6 ..3 (theo (1.1)), nên . 3k+2 .M 6 ..3k+3 b) Do k ≥ 2, nên ∃t ∈ N (k = t + 2) và 32k+1 .M 2 = 3k+3+t .M 2 . Bởi vậy . 32k+1 .M 2 ..3k+3 k k. k. k Giả sử 23 ..3k+3 . Khi đó 23 ..9, nhưng 23 = 23 = 8k = ±1 (mod 9), nên k . 23 6 ..3k+3 Từ các quan hệ (1.3) và (1.4) ta suy ra  k 32k+1 .M 2 − 23  . 6 ..3k+3 (1.2) (1.3) (1.4) (1.5) . Từ (1.2) và (1.5) suy ra: Ak+1 6 ..3k+3 , nên với mọi số nguyên dương n số An không chia hết cho 3n+2 .  Ví dụ 1.2.6. (Chứng minh bất đẳng thức bằng quy nạp) Cho n(n ≥ 1) số dương x1 , x2 , · · · , xn thỏa mãn điều kiện x1 .x2 . · · · xn−1 .xn = 1 Chứng minh rằng x1 + x2 + · · · + xn−1 + xn ≥ n và dấu đẳng thức xảy ra khi và chỉ khi x1 = x2 = · · · = xn 7 Chương 1. Phương pháp quy nạp Lời giải: Bài toán được giải quyết bằng quy nạp. 1) Cơ sở quy nạp. Với n = 1 ta chỉ có số x1 . Vì x1 = 1, nên x1 thỏa mãn bất đẳng thức x1 ≥ 1. 2) Quy nạp. Giả sử khẳng định đã đúng với k số dương tùy ý có tích bằng 1. Xét k + 1 số dương tùy ý x1 , x2 , · · · , xk , xk+1 với x1 .x2 . · · · xk .xk+1 = 1. Có hai khả năng đặt ra: a) Nếu x1 = x2 = · · · = xk = xk+1 , thì xi = 1 (1 ≤ i ≤ k + 1). Khi đó x1 + x2 + · · · + xk + xk+1 = k + 1 và khẳng định được chứng minh. b) Nếu k + 1 số được xét x1 , x2 , · · · , xk , xk+1 không đồng thời bằng nhau, thì do tích của chúng bằng 1 và các số này đều dương, phải có ít nhất một số lớn hơn 1 và ít nhất một số nhỏ hơn 1. Không giảm tính tổng quát, giả sử xk < 1 và xk+1 > 1. Khi đó 1 − xk > 0, xk+1 − 1 > 0 nên (1 − xk ) (xk+1 − 1) > 0 Bởi vậy xk + xk+1 > xk .xk+1 + 1 (1.6) Từ đẳng thức: x1 .x2 . · · · xk−1 (xk xk+1 ) = x1 .x2 . · · · .xk−1 xk .xk+1 = 1 suy ra k số dương x1 , x2 , · · · , xk−1 , (xk xk+1 ) có tích bằng 1, nên theo giả thiết quy nạp, có x1 + x2 + · · · + xk xk+1 ≥ k Cộng cả hai vế của bất đẳng thức trên với 1 ta có bất đẳng thức x1 + x2 + · · · + xk xk+1 + 1 ≥ k + 1 (1.7) Từ bất đẳng thức (1.6) và (1.7) ta có x1 + x2 + · · · + xk + xk+1 ≥ x1 + x2 + · · · + xk xk+1 + 1 ≥ k + 1 Khẳng định đã được chứng minh. Với n số dương tùy ý x1 = x2 = · · · = xn và x1 .x2 . · · · xn = 1 suy ra xi = 1(1 ≤ i ≤ n), nên x1 + x2 + · · · + xn = n.  Ví dụ 1.2.7. (Tìm chữ số tận cùng bằng quy nạp) k Với mọi số nguyên dương k ≥ 2 hãy tìm chữ số tận cùng của số Ak = 22 + 1. 8 Chương 1. Phương pháp quy nạp Lời giải: Bài toán được giải quyết bằng quy nạp. 2 1) Cơ sở quy nạp. Với k = 2 số A2 = 22 + 1 = 24 + 1 = 17 2) Quy nạp. Giả sử với k = n ≥ 2 số An đã có tận cùng là 7. n+1 Xét số An+1 = 22 + 1. Do An tận cùng số 7, nên tồn tại số nguyên dương m, để An = 10m + 7. Từ đó n An − 1 = 22 = 10m + 6. n+1 An+1 = 22 n.2 + 1 = 22 n + 1 = 22 2 +1 = (10m + 6)2 + 1 = 100m2 + 120m + 36 + 1 = 10 10m2 + 12m + 37 = 10 10m2 + 12m + 3 + 7  nên An+1 tận cùng bằng chữ số 7. Vậy với mọi số k ≥ 2, số Ak tận cùng bằng chữ số 7.  Ví dụ 1.2.8. Tính tổng sau S(n) = 12 + 32 + · · · + (2n + 1)2 , trong đó n là một số tự nhiên. Lời giải: Ta sẽ đi dự đoán công thức tổng S(n). Ta thấy S(n) là tổng của các lũy thừa bậc hai của các số 1, 3, · · · , (2n + 1), nên ta dự đoán S(n) phải là một đa thức của n có bậc không nhỏ hơn ba. Giả sử S(n) = an3 + bn2 + cn + d. Vì S(0) = 1 nên d = 1. Lần lượt thay n = 1, n = 2, n = 3, ta được hệ  a+b+c=9   8a + 4b + 2c = 34 27a + 9b + 3c = 83 Giải hệ này ta thu được a = 34 , b = 4, c = 11 3. Khi đó, 4 11 (n + 1) (2n + 1) (2n + 3) S(n) = n3 + 4n2 + n + 1 = 3 3 3 (1.8) Ta sẽ chứng minh công thức (1.8) bằng quy nạp theo n. 1) Cơ sở quy nạp. Với n = 0, 1, 2, 3, 4, 5, ta dễ dàng kiểm tra được (1.8) đúng. 2) Quy nạp. Giả sử (1.8) đúng với n = k , ta chứng minh (1.8) đúng với n = k + 1. Thật vậy S(k + 1) = 12 + 32 + · · · + (2k + 1)2 + (2k + 3)2 = S(k) + (2k + 3)2 . 9 Chương 1. Phương pháp quy nạp Theo giả thiết quy nạp thì S(k) = Suy ra (k+1)(2k+1)(2k+3) . 3 (k + 1) (2k + 1) (2k + 3) + (2k + 3)2 3 (k + 2) (2k + 3) (2k + 5) = 3 S(k + 1) = Vậy công thức (1.8) đúng với n = k + 1, do đó theo nguyên lý quy nạp (1.8) đúng với mọi n. Ví dụ 1.2.9. Chứng minh rằng A(n) = 7n + 3n − 1 chia hết cho 9 với mọi số tự nhiên n. Lời giải: Đặt A(n) = 7n + 3n − 1. Ta sẽ chứng minh bài toán bằng quy nạp. 1) Cơ sở quy nạp. Với n = 0, ta có A(0) = 0 chia hết cho 9. 2) Quy nạp. Giả sử A(k) chia hết cho 9 với mọi k ∈ N. Ta sẽ chứng minh A(k + 1) cũng chia hết cho 9. Thật vậy, ta có A(k + 1) = 7k+1 + 3 (k + 1) − 1 = 7A(k) − 9. (2k − 1) . (1.9) Theo giả thiết quy nạp thì A(k) chia hết cho 9. Do đó từ (1.9) ta suy ra A(k + 1) cũng chia hết cho 9. Vậy A(n) chia hết cho 9 với mọi số tự nhiên n.  Ví dụ 1.2.10. Gọi S(n) là tổng tất cả các ước số lẻ lớn nhất của các số tự nhiên từ 1 đến 2n . Chứng minh rằng 3S(n) = 4n + 2. Lời giải: Các số tự nhiên từ 1 đến 2n bao gồm các số lẻ từ 1 đến 2n và gấp đôi của các số tự nhiên từ 1 đến 2n−1 . Từ đó ta có S(n) = S(n − 1) + 1 + 3 + · · · + (2n − 1) hay S(n) = S(n − 1) + 4n−1 (1.10) Ta sẽ chứng minh bài toán đã cho bằng quy nạp theo n. 1) Cơ sở quy nạp. Với n = 1, ta có 3S(1) = 3(1 + 1) = 6 = 41 + 2, khẳng định đúng với n = 1 10 Chương 1. Phương pháp quy nạp 2) Quy nạp. Giả sử khẳng định đúng với n = k , tức là (1.11) 3S(k) = 4k + 2 Ta cần chỉ ra khẳng định đúng với n = k + 1 hay 3S(k + 1) = 4k+1 + 2. Thật vậy, theo (1.10) ta có S(k + 1) = S(k) + 4k ⇔ 3S(k + 1) = 3S(k) + 3.4k (1.12) = 4k + 2 + 3.4k = 4k+1 + 2. theo giả thiết quy nạp. Vậy khẳng định đã cho đúng với mọi n ∈ N∗ .  Ví dụ 1.2.11. Tìm bậc cao nhất k của 2007 sao cho 2007k là ước của số: 2006 20082007 2008 + 20062007 . Lời giải: Ta chứng minh hai bổ đề sau: Bổ đề 1.2.1. Với số tự nhiên lẻ a ≥ 3 và với mọi n nguyên dương không chia hết cho a, ta có: n (1 + a)a = 1 + Sn an+1 , trong đó Sn là số nguyên dương và không chia hết cho a. Bổ đề 1.2.2. Với số tự nhiên lẻ b ≥ 3 và với mọi số n nguyên dương, ta có: n (b − 1)b = −1 + tn bn+1 , trong đó tn là số nguyên không chia hết cho b. +, Chứng minh bổ đề 1: Ta sẽ chứng minh bổ đề 1 bằng quy nạp. 1. Cơ sơ quy nạp. Với n = 1, ta có (1 + a)a = 1 + Ca1 a + Ca2 a2 + . . . + Caa aa = = 1 + a2 1 + Ca2 + Ca3 a + . . . + aa−2 = 1 + S1 a2 . a(a−1) . a! = 2 ..a. Vì a lẻ nên Ca2 = 2!(a−2)! Do vậy, S1 = 1 + Ca2 + Ca3 a + . . . + aa−2 không chia hết cho a. 11  Chương 1. Phương pháp quy nạp 2. Quy nạp. Giả sử khẳng định trên đúng với n = k , tức là k (1 + a)a = 1 + Sk ak+1 , trong đó Sk là số nguyên dương và không chia hết cho a. Ta có  ak+1 ak .a k+1 a (1 + a) = (1 + a)  = 1 + Sk a = 1 + Ca1 Sk ak+1 + Ca2 Sk ak+1 2 + . . . + Caa Sk ak+1 = 1 + ak+2 Sk + Ca2 Sk2 + . . . + Ska aak+a−k−2  = 1 + Sk+1 ak+2 .  a  Vì Sk không chia hết cho a suy ra Sk+1 không chia hết cho a. Vậy bổ đề được chứng minh. +, Chứng minh bổ đề 2. Bổ đề 2 được chứng minh bằng phương pháp quy nạp bằng cách lý luận tương tự như chứng minh bổ đề 1. Áp dụng hai bổ đề trên với a = b = 2007, ta được 2006 20082007 2008 + 20062007 = S2006 20072007 + t2008 20072009 = S2006 + t2008 20072 20072007 .  Vì S2006 không chia hết cho 2007 nên số k lớn nhất thỏa mãn điều kiện bài toán là 2007. Ví dụ 1.2.12. Dãy số (un ) xác định như sau:  un+1 u0 = u1 = 1 = un−1 un + 1; n = 1, 2, . . . . Chứng minh rằng: u2008 − 3..4. Lời giải: Từ cách xác định dãy số, ta có u2 = 2; u3 = 3; u4 = 7; u5 = 22; u6 = 155; . . . Nhận thấy: u2 ≡ 2 (mod 4); u5 ≡ 2 (mod 4). u3 ≡ 3 (mod 4); u4 ≡ 3 (mod 4). Ta dự đoán:  un ≡ 2 un ≡ 3 (mod 4) nếu n = 3k + 2, (k ∈ Z) (mod 4) nếu n = 3k + 1 hoặc n = 3k , (k ∈ Z). 12 (1.13) Chương 1. Phương pháp quy nạp Ta sẽ chứng minh quan hệ (1.13) bằng quy nạp. 1. Cơ sở quy nạp. Với n = 2, 3, 4, 5, ta có quan hệ (1.13) đúng. 2. Quy nạp. Giả sử (1.13) đúng với n = t. Ta cần chứng minh (1.13) đúng với n = t + 1. +) Nếu t = 3k , khi đó  t − 1 = 3k − 1 = 3(k − 1) + 2 t + 1 = 3k + 1. Do đó, theo giả thiết quy nạp ta có ut ≡ 3 (mod 4); ut−1 ≡ 2 (mod 4) Suy ra ut+1 ≡ 3.2 + 1 ≡ 3 (mod 4), hay (1.13) đúng. +) Nếu t = 3k + 1, suy ra  t − 1 = 3k t + 1 = 3k + 2 . Do đó, theo giả thiết quy nạp ta có ut ≡ 3 (mod 4); ut−1 ≡ 3 (mod 4) Suy ra ut+1 ≡ 3.3 + 1 ≡ 2 (mod 4), hay (1.13) đúng. +) Nếu t = 3k + 2, suy ra  t − 1 = 3k + 1 t + 1 = 3(k + 1) . Do đó, theo giả thiết quy nạp ta có ut ≡ 2 (mod 4); ut−1 ≡ 3 (mod 4) Suy ra ut+1 ≡ 3.2 + 1 ≡ 3 (mod 4), hay (1.13) đúng. Vậy (1.13) được chứng minh. Do 2008 = 3.669 + 1, nên u2008 ≡ 3 . (mod 4), hay u2008 − 3..4.  13 Chương 1. Phương pháp quy nạp Ví dụ 1.2.13. Chứng minh rằng số được thành lập bởi 3n chữ số giống nhau thì chia hết cho 3n , trong đó n là một số nguyên dương cho trước. Lời giải: Gọi A(n) = aa . . . a, trong đó A(n) gồm 3n chữ số a và 1 ≤ a ≤ 9. Ta chứng minh khẳng định bằng quy nạp theo n. 1. Cơ sở quy nạp. Với n = 1, ta có A(1) = aaa chia hết cho 31 = 3. Khẳng định đúng với n = 1. 2. Quy nạp. Giả sử A(n) chia hết cho 3n , ta cần chứng minh A(n + 1) chia hết cho 3n+1 . Thật vậy, ta có n n A(n + 1) = A(n)A(n)A(n) = A.102.3 + A.103 + A n n = A 102.3 + 103 + 1 .  Vì 10 ≡ 1 (mod 3) nên 102.3 + 103 + 1 ≡ 0 (mod 3). Hơn nữa, theo giả thiết quy nạp, A(n) chia hết 3n . Do đó, ta có A(n + 1) chia hết 3n .3 = 3n+1 , hay khẳng định đúng với n + 1. Theo nguyên lý quy nạp, khẳng định đã cho đúng với mọi n ∈ Z+ . n n  Ví dụ 1.2.14. Mỗi đầu của đường kính thuộc đường tròn tâm 0 ghi số 1. Sau đó tại trung điểm của mỗi cung nhận được ghi số 2 (tổng của hai số được ghi ở hai đầu của mỗi cung) (Bước 2). Coi bốn điểm ghi số là các điểm chia đường tròn. Khi đó đường tròn được chia thành bốn cung bằng nhau. Giữa mỗi cung này lại ghi số 3 (tổng của hai số được ghi ở hai đầu của cung tương ứng) (Bước 3). Cứ tiếp tục như vậy. Hỏi sau n bước tổng các số được ghi trên đường tròn là bao nhiêu? 2 3 3 1 1 0 3 3 2 14 Chương 1. Phương pháp quy nạp Lời giải: Sau n bước tổng các số trên đường tròn là Sn = 2.3n . Ta sẽ chứng minh công thức trên bằng quy nạp theo n. 1. Cơ sở quy nạp. Sau Bước 1, trên đường tròn có bốn (22 ) số 1, 2, 1, 2. Khi đó S1 = 1 + 2 + 1 + 2 = 6 = 2.31 2. Quy nạp. Giả sử khẳng định đúng với n = k(k ≥ 1), nghĩa là sau k bước trên đường tròn đã có 2k+1 số (1.14) s1 , s2 , . . . , s2k +1 , . . . , s2k+1 , với tổng là Sk = 2.3k . 2 3 3 1 1 3 3 2 Sang bước (k + 1), ta coi 2k+1 điểm đã ghi là các điểm chia, nên đường tròn được thành 2k+1 cung bằng nhau. Do trung điểm của mỗi cung này lại ghi tổng của hai số đã ghi ở đầu của mỗi cung, nên mỗi số thuộc dãy (1.14) được xuất hiện đúng hai lần trong các tổng mới (các số được ghi tại bước k + 1). Do đó, tổng các số được ghi trên đường tròn sau k + 1 bước là: Sk+1 = tổng các số đã ghi sau bước k + tổng các số được ghi tại bước k+1 = Sk + 2Sk = 3Sk = 3.2.3k = 2.3k+1 Khẳng định được chứng minh.  Ví dụ 1.2.15. Chứng minh rằng trên mặt phẳng n đường thẳng khác nhau cùng đi qua một điểm, chia mặt phẳng thành 2n phần khác nhau. Lời giải: Bài toán được giải quyết bằng quy nạp. 1) Cơ sở quy nạp. Với n = 1, ta có một đường thẳng. Nó chia mặt phẳng thành hai phần, nên khẳng định đúng. 15 Chương 1. Phương pháp quy nạp 2) Quy nạp. Giả sử với n = k khẳng định đã đúng, nghĩa là k đường thẳng tùy ý cùng đi qua một điểm M đã chia mặt phẳng thành 2k phần khác nhau. Xét n = k + 1 đường thẳng khác nhau tùy ý cùng đi qua một điểm. Kí hiệu các đường này, một cách tương ứng bằng δ1 , δ2 , · · · , δk , δk+1 . Theo giả thiết quy nạp k đường thẳng δ1 , δ2 , · · · , δk đã chia mặt phẳng thành 2k phần khác nhau. δs M δk+1 δt Vì các đường thẳng đều khác nhau và cùng đi qua điểm M , nên tồn tại các chỉ số s, t (1 ≤ s, t ≤ k) để δk+1 là đường thẳng duy nhất nằm trong góc được lập nên bởi δs và δt . Khi đó δk+1 chia hai phần mặt phẳng được giới hạn bởi δs và δt thành bốn phần. Bởi vậy k + 1 đường thẳng δ1 , δ2 , · · · , δk , δk+1 chia mặt phẳng thành 2k − 2 + 4 = 2k + 2 = 2 (k + 1) phần khác nhau. Khẳng định được chứng minh. 16 
- Xem thêm -