Luận văn Thạc sĩ Toán học: Quy nạp và phương pháp quy nạp toán học trong hình học

Chia sẻ: Huyen Nguyen My | Ngày: | Loại File: PDF | Số trang:79

Thêm vào BST

Báo xấu

103
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục tiêu nghiên cứu của luận văn này là trình bày khái quát các kết quả chính đã có về quy nạp Toán học và phương pháp quy nạp Toán học.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Quy nạp và phương pháp quy nạp toán học trong hình học

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC THĂNG LONG PHẠM THỊ UYÊN QUY NẠP VÀ PHƯƠNG PHÁP QUY NẠP TOÁN HỌC TRONG HÌNH HỌC LUẬN VĂN THẠC SĨ TOÁN HỌC HÀ NỘI - 2019
BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC THĂNG LONG PHẠM THỊ UYÊN-C01093 QUY NẠP VÀ PHƯƠNG PHÁP QUY NẠP TOÁN HỌC TRONG HÌNH HỌC CHUYÊN NGÀNH: PHƯƠNG PHÁP TOÁN SƠ CẤP MÃ SỐ:8 46 01 13 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: TS. Nguyễn Văn Đoành HÀ NỘI - 2019 Thang Long University Library
i Lời cam đoan Luận văn này là kết quả nghiên cứu của bản thân tôi dưới sự hướng dẫn tận tình của TS Nguyễn Văn Đoành. Trong khi nghiên cứu hoàn thành luận văn này tôi đã tham khảo một số tài liệu đã ghi trong phần tài liệu tham khảo. Tôi xin khẳng định kết quả của luận văn "Quy nạp và phương pháp quy nạp Toán học trong hình học" là kết quả của việc nghiên cứu, học tập và nỗ lực của bản thân, không có sự trùng lặp với kết quả của các luận văn khác. Nếu sai tôi xin hoàn toàn chịu trách nhiệm. Hà Nội, ngày tháng 9 năm 2019 Người viết luận văn Phạm Thị Uyên
ii Lời cảm ơn Trước khi trình bày nội dung chính của luận văn, tôi xin được bày tỏ lòng biết ơn sâu sắc tới TS.Nguyễn Văn Đoành, người đã tận tình hướng dẫn, giúp đỡ, động viên tôi hoàn thành được luận văn này. Trong suốt quá trình làm luận văn, thầy đã dành nhiều thời gian và công sức để chỉ bảo hướng dẫn tôi từ những điều nhỏ nhặt tới những vấn đề khó khăn, thầy vẫn luôn kiên nhẫn, tận tình quan tâm giúp đỡ tôi để hoàn thành luận văn này. Tôi cũng xin gửi lời cảm ơn sâu sắc tới các thầy cô thuộc Khoa Toán, Trường Đại học Thăng Long, những người đã tận tình giảng dạy và khích lệ, động viên tôi vượt qua những khó khăn trong học tập. Tôi xin cảm ơn Ban giám hiệu Trường Đại học Thăng Long, khoa Sau đại học và các học viên lớp Cao học khóa K6.1 đã tạo mọi điều kiện thuận lợi giúp đỡ chúng tôi trong suốt thời gian học tập. Cuối cùng tôi xin cảm ơn bạn bè, đồng nghiệp, và người thân đã tạo điều kiện, động viên, khích lệ, giúp đỡ, ủng hộ để tôi có thể hoàn thành tốt khóa học của mình. Hà Nội, ngày tháng 9 năm 2019 Người viết luận văn Phạm Thị Uyên Thang Long University Library
iii Mục lục Lời cam đoan i Lời cảm ơn ii Mục lục iii Mở đầu 1 1 Phương pháp quy nạp Toán học 3 1.1. Suy luận và chứng minh Toán học . . . . . . . . . . 3 1.1..1 Suy luận Toán học . . . . . . . . . . . . . . . . 3 1.1..2 Các phương pháp chứng minh . . . . . . . . . 6 1.1..3 Phương pháp chứng minh quy nạp Toán học 11 1.2. Suy luận quy nạp . . . . . . . . . . . . . . . . . . . . . 17 1.2..1 Phương pháp quy nạp hoàn toàn . . . . . . . . . . 18 1.2..2 Quy nạp không hoàn toàn và các giả thuyết Toán học . . . . . . . . . . . . . . . . . . . . . . 19 1.3. Phương pháp quy nạp toán học ở trường phổ thông 21 2 Phương pháp quy nạp trong hình học 25 2.1. Tính toán bằng quy nạp . . . . . . . . . . . . . . . . . 25 2.2. Chứng minh bằng quy nạp.Tô màu bản đồ . . . . . 32 2.2..1 Chứng minh bằng quy nạp . . . . . . . . . . . 32
iv 2.2..2 Tô màu bản đồ . . . . . . . . . . . . . . . . . . 36 2.3. Xây dựng định nghĩa nhờ quy nạp . . . . . . . . . . 55 2.3..1 Trung tuyến và trọng tâm của n-giác . . . . . 55 2.3..2 Đường tròn Euler của n-giác . . . . . . . . . . 58 2.3..3 Đường thẳng Simson của n-giác nội tiếp . . . 62 2.3..4 Điểm ceva của n-giác . . . . . . . . . . . . . . . 63 Tài liệu tham khảo 73 Thang Long University Library
1 Mở đầu Suy luận quy nạp là suy luận trên cơ sở khảo sát các trường hợp riêng để đi đến các giả thuyết. Suy luận quy nạp Toán học có vai trò quan trọng trong Toán học và các nghành khoa học khác. Suy luận quy nạp cũng đã được sử dụng trong giải các dạng toán như một cách gợi mở, tìm tòi phát hiện vấn đề. Phương pháp quy nạp Toán học cũng đã được đưa vào chương trình phổ thông, giới thiệu một cách chứng minh có quy tắc và rất hiệu quả. Để nâng cao khả năng tư duy Toán học và tìm hiểu thêm phương pháp quy nạp Toán học trong hình học, chương trình phổ thông, tôi chọn đề tài luận văn cao học là “ Quy nạp và phương pháp quy nạp Toán học trong hình học ”. Trong luận văn này, tôi xin trình bày khái quát các kết quả chính đã có về quy nạp Toán học và phương pháp quy nạp Toán học. Bố cục của luận văn gồm 2 chương: Chương 1 Phương pháp quy nạp Toán học Chương 2 Phương pháp quy nạp trong hình học Do thời gian nghiên cứu có hạn, luận văn không thể tránh khỏi những thiếu sót, tác giả rất mong nhận được những ý kiến đóng góp của các thầy và các bạn để luận văn được hoàn thiện hơn. Xin chân thành cảm ơn!
2 Hà Nội, ngày tháng năm 2019 Người thực hiện Phạm Thị Uyên Thang Long University Library
3 Chương 1 Phương pháp quy nạp Toán học 1.1. Suy luận và chứng minh Toán học 1.1..1 Suy luận Toán học a.Quy tắc suy luận Định nghĩa 1.1. Cho A1 , A2 , A3 , ...., An và B là những mệnh đề. Ta nói rằng có một quy tắc suy luận với các tiền đề là A1 , A2 , A3 , ...., An và hệ V V V V quả logic là B nếu ( A1 A2 A3 .... An ) →B là một mệnh đề hằng đúng A1 , A2 , ..., An Quy tắc suy luận trên đây được kí hiệu là hoặc B A1 .. . An ∴B V Hằng đúng (p (p → q)) → q là cơ sở của quy tắc suy luận có tên là Modus ponens hay luật tách rời. Hằng đúng này được viết như sau : p p→q ∴q
4 Khi dùng ký hiệu này, các giả thiết được viết trên dấu gạch ngang còn kết luận viết dưới dấu gạch ngang. Ký hiệu “∴ ” có nghĩa là “ vậy thì” . Luật tách rời phát biểu rằng nếu cả mệnh đề kéo theo và các giả thiết của nó là đúng suy ra kết luận của mệnh đề là đúng. Ví dụ 1.1. Mệnh đề kéo theo “ nếu n chia hết cho 3 ” thì “ n2 chia hết cho 9 ”là đúng. Do vậy nếu n chia hết cho 3, thì theo luật tách rời ta suy ra n2 chia hết cho 9. Bảng 1.1: Bảng liệt kê một số quy tắc quan trọng Quy tắc suy luận Hằng đúng Tên gọi p p → (p ∨ q) Luật công ∴p∨q p∧q (p ∧ q) → p Luật rút gọn ∴p p p→q [p ∧ (p → q)] → q Luật tách rời ∴q ¬q p→q [¬q ∧ (p → q)] → ¬p Luật phản chứng ∴ ¬p p→q q→r [(p → q) ∧ (q → r)] → (p → r) Luật bắc cầu ∴p→r p∨q ¬p [(p ∨ q) ∧ ¬p] → q Luật loại trừ ∴q b. Ngụy biện Có một số ngụy biện rất hay gặp trong chứng minh sai. Chúng giống như các suy luận không dựa trên những mệnh đề hằng đúng mà chỉ là những Thang Long University Library
5 mệnh đề tiếp liên. Bây giờ ta sẽ chỉ ra sự khác nhau giữa suy luận đúng và suy luận sai •Mệnh đề [(p → q) ∧ q] → p không là hằng đúng vì nó sai khi p sai và q đúng. Tuy nhiên, có nhiều chứng minh sai xem nó như hằng đúng. Sở dĩ có sai lầm này là người ta cho rằng mệnh đề p → q tương đương với mệnh đề q → p nên khi có q đúng suy ra p đúng. Loại suy luận sai điển hình này gọi là ngộ nhận kết luận Ví dụ 1.2. p : “n chia 3 dư 1 ” q :“ n2 chia 3 dư 1 ” p → q : “n chia 3 dư 1 thì n2 chia 3 dư 1 ”là mệnh đề đúng Nếu q đúng, tức là n2 chia 3 dư 1 có thể suy ra p đúngtức là n chia 3 dư 1 không? Lời giải : Không thể kết luận p đúng được bởi vì n có thể chia 3 dư 2, khi đó n2 = (3k + 2)2 = 9k 2 + 12k + 4 = 3(3k 2 + 4k + 1) + 1 chia 3 dư 1. Chứng minh sai vì đã ngộ nhận kết luận •Mệnh đề [(p → q) ∧ ¬p] → ¬q không phải là hằng đúng vì nó sai khi p sai và q đúng. Nhiều chứng minh sai vì đã sử dụng mệnh đề này như một luật suy diễn.Sở dĩ có sai lầm này là do người ta cho rằng mệnh đề p → q tương đương với mệnh đề ¬p → ¬q nên khi có ¬p đúng suy ra ¬q đúng. Loại suy diễn sai lầm kiểu này gọi là ngụy biện phủ nhận giả thiết Ví dụ 1.3. Suy diễn sau đây có đúng hay không ? Nếu x > 1 thì x2 > 1 Ta có x ≤ 1vậy thì x2 ≤ 1 Lời giải : Giả sử p là mệnh đề “ x > 1” còn q là mệnh đề “ x2 > 1”. Khi đó, cách suy diễn trên có dạng : [(p → q) ∧ ¬p] → ¬q . Đây là suy diễn sai dạng ngụy biện phủ nhận giả thiết. Thật vậy, ta có x = −2 nhỏ hơn 1 nhưng x2 = 4 lớn hơn 1 •Suy luận quẩn : Ngụy biện này xuất hiện khi chứng minh một mệnh đề lại sử dụng chính nó hoặc một mệnh đề tương đương với nó
6 Ví dụ 1.4. Chứng minh tiên đề Ơclit về đường song song •Ngoài những ngụy biện nêu trên còn có những suy luận sai do áp dụng không đúng các định lý hoặc tính chất. 1.1..2 Các phương pháp chứng minh Dưới đây, chúng ta sẽ mô tả cách chứng minh các kiểu mệnh đề kéo theo p → q , nên các kỹ thuật chứng minh kéo theo là rất quan trọng. Sau đây ta sẽ bàn tới những kĩ thuật chứng minh phép kéo theo • Chứng minh rỗng Giả sử rằng giả thiết p của phép kéo theo p → q là sai. Khi đó, phép kéo theo là đúng vì hai dạng mệnh đề F → T và F → F đều đúng. Do vậy, nếu có thể chỉ ra p là sai thì phép kéo theo p → q được chứng minh. Một chứng minh như vậy được gọi là chứng minh rỗng Ví dụ 1.5. Chỉ ra rằng mệnh đề P (0) là đúng, trong đó P (n) là hàm mệnh đề “ Nếu n > 1 thì n2 > n ” Lời giải : Dễ thấy P (0) là mệnh đề kéo theo “ nếu 0 > 1 thì 02 > 0 ”. Vì giả thiết 0 > 1 sai nên mệnh đề kéo theo P (0) tự động đúng. Chú ý rằng kết luận của phép kéo theo 02 > 0 là sai. Nhưng không vì thế mà mệnh đề P (0) là sai, vì theo định nghĩa, mệnh đề kéo theo chỉ sai khi giả thiết của nó đúng còn kết luận của nó là sai. •Chứng minh tầm thường Giả sử rằng kết luận q của phép kéo theo p → q là đúng. Khi đó p → q là đúng vì nó có dạng T → T hoặc F → T đều đúng cả. Do vậy, nếu có thể chỉ ra được q là đúng thì mệnh đề p → q được chứng minh. Một chứng minh như vậy gọi là chứng minh tầm thường Ví dụ 1.6. Gọi P (n) là mệnh đề “ Nếu a và b là hai số nguyên dương và a ≥ b thì an ≥ bn ”.Hãy chỉ ra rằng P (0) là đúng. Lời giải : Mệnh đề P (0) là câu :“ Nếu a và b là hai số nguyên dương và a Thang Long University Library
7 ≥b thì a0 ≥b0 ” . Do đó P (0) là đúng. Đây là một ví dụ về chứng minh tầm thường •Chứng minh trực tiếp Cách chứng minh thông thường hơn hai cách chứng minh trên là cho p đúng rồi sử dụng các suy luận có lý để chỉ ra rằng q cũng đúng, tức là tổ hợp p đúng q sai không bao giờ xảy ra. Chứng minh này gọi là chứng minh trực tiếp Ví dụ 1.7. Hãy chứng minh trực tiếp mệnh đề “ Nếu n là số lẻ thì n2 cũng là số lẻ ” . Lời giải : Giả sử rằng giả thiết của mệnh đề kéo theo này là đúng. Khi đó n = 2k + 1, với k là số nguyên. Từ đó suy ra n2 = (2k + 1)2 = 4k 2 + 4k + 1 = 2(2k 2 + 2k) + 1, do đó n2 cũng là số lẻ • Chứng minh gián tiếp Ta biết rằng hai mệnh đề tương đương logic với nhau nếu và chỉ nếu tính đúng sai của chúng như nhau. Vì vậy để chứng minh một mệnh đề M đã cho là đúng, ta có thể chứng minh một mệnh đề tương đương logic với M là đúng. Chẳng hạn để chứng minh mệnh đề p → q là đúng, ta có thể chứng minh mệnh đề ¬q→ ¬p là đúng. Vì mệnh đề kéo theo p→q tương đương với mệnh đề phản đảo của nó là ¬q→ ¬p, nên phép kéo theo sẽ được chứng minh bằng cách chỉ ra rằng mệnh đề ¬q→ ¬p là đúng.Mệnh đề kéo theo này thường được chứng minh trực tiếp nhưng cũng có thể sử dụng bất cứ kỹ thuật chứng minh nào. Chứng minh kiểu này gọi là chứng minh gián tiếp Ví dụ 1.8. Hãy chứng minh gián tiếp định lý “ Nếu 3n + 2 là một số lẻ thì n cũng là số lẻ ” Lời giải : Giả sử ngược lại kết luận của phép kép theo là sai, tức n chẵn. Khi đó n = 2k với k là số nguyên nào đó. Từ đó suy ra 3n + 2 = 3(2k) + 2 = 2(3k + 1) và do đó 3n + 2 là số chẵn. Vậy
8 phủ định kết luận của phép kéo theo dẫn đến phủ định của giả thiết của nó, nên mệnh đề kéo theo ban đầu là đúng. •Chứng minh bằng phản chứng Ta có [¬p → (q ∧ ¬q)] → p là một mệnh đề hằng đúng do đó có một quy tắc suy luận ¬p → (q ∧ ¬q) ∴p Như vậy để chứng minh mệnh đề p đã cho là đúng, ta giả sử p sai, tức ¬pđúng từ đó suy ra hai mệnh đề q và ¬q, tức là suy ra mệnh đề hằng sai q∧¬q.Ta biết rằng ¬p→F là đúng chỉ trong trường hợp ¬p sai do đó p đúng. Kiểu chứng minh này gọi là chứng minh bằng phản chứng Ví dụ 1.9. Hãy chứng minh bằng phản chứng định lý : “ Nếu a là số vô tỷ thì b = a+2 là số vô tỷ. ” m Lời giải : Giả sử b = a+2 là số hữu tỷ thì b = với m, n là số nguyên. n m m − 2n Khi đó từ đẳng thức b = a + 2 suy ra a = b − 2 = −2 = là n n số hữu tỷ. Điều này mẫu thuẫn với giả thiết a là số vô tỷ. Định lý được chứng minh •Chứng minh bằng cách xét từng trường hợp Để chứng minh mệnh đề có dạng (p1 ∨ p2 ∨ · · · ∨ pn ) → q là đùng người ta dùng hằng đúng [(p1 ∨ p2 ∨ · · · ∨ pn → q] ↔ [(p1 → q) ∧ (p2 → q) ∧ · · · ∧ (pn → q)] Điều này chứng tỏ mệnh đề kéo theo có giả thiết là tuyển của các mệnh đề p1 , p2 , · · · , pn có thể được chứng minh mỗi một trong n mệnh đề kéo theo pi → q với i = i, n một cách riêng rẽ. Cách chứng minh như trên gọi là chứng minh từng trường hợp Ví dụ 1.10. Hãy chứng minh mệnh đề “ Nếu số nguyên n không chia hết cho 3 thì n2 chia 3 dư 1”. Thang Long University Library
9 Lời giải: Gọi p là mệnh đề : “ n không chia hết cho 3 ” và q là mệnh đề “ n2 chia 3 dư 1 ”. Khi đó p tương đương với p1 ∨ p2 trong đó p1 là mệnh đề “ n chia 3 dư 1 ” còn p2 là mệnh đề : “ n chia 3 dư 2 ”. Từ đó để chứng tỏ p → q ta sẽ chứng minh p1 → q và p2 → q . Hai mệnh đề kéo theo này được chứng minh dễ dàng như sau : Giả sử p1 đúng, tức là n = 3k + 1 với k là một số nguyên nào đó. Khi đó : n2 = 9k 2 + 6k + 1 = 3(3k 2 + 2k) + 1, tức là “ n2 chia 3 dư 1 ” hay p1 → q là đúng Tiếp theo giả sử p2 là đúng, tức là n = 3k + 2 với k là một số nguyên nào đó. Khi đó : n2 = 9k 2 + 12k + 4 = 3(3k 2 + 2k + 1) + 1, tức là “ n2 chia 3 dư 1 ” hay p2 → q là đúng. Vì cả hai mệnh đề (p1 → q) và (p2 → q) là đúng nên kết luận (p1 ∨p2 ) → q là đúng. Hơn thế nữa, vì p tương đương với p1 ∨ p2 nên suy ra mệnh đề p → q là đúng. •Chứng minh mệnh đề tương đương Để chứng minh định lý có dạng cần và đủ, tức là nó có dạng p ↔ q , trong đó p và q là hai mệnh đề, ta sử dụng hằng đúng: (p ↔ q) ↔ [(p → q) ∧ (q → p)]. Tức là mệnh đề “ p nếu và chỉ nếu q ” là đúng nếu cả hai mệnh đề kéo theo “ nếu p thì q ” và “ nếu q thì p ” được chứng minh là đúng. Ví dụ 1.11. Hãy chứng minh định lý “ a4 = b4 khi và chỉ khi a2 = b2 ” Lời giải: Định lý này có dạng “ p nếu và chỉ nếu q ”, trong đó p là mệnh đề “ a4 = b4 ” còn q là mệnh đề “ a2 = b2 ” . Để chứng minh định lý này, ta chỉ cần chỉ ra p → q và q → p là đúng. Để chứng minh phép kéo theo thứ nhất ta giả sử p đúng, tức là a4 = b4 . Suy ra a4 − b4 = (a2 + b2 )(a2 − b2 ) = 0. Mệnh đề này tương đương với
10 mệnh đề p1 ∨ p2 , trong đó p1 = a2 + b2 = 0 và p2 = a2 − b2 = 0. Nếu p1 đúng tức là a2 + b2 = 0 suy ra a = b = 0.Do đó a2 = b2 = 0 do đó q đúng. Nếu p2 đúng, tức là a2 − b2 = 0 suy ra a2 = b2 , tức là q đúng. Như vậy, mệnh đề kéo theo thứ nhất đã được chứng minh. Để chứng minh mệnh đề kéo theo thứ hai, ta giả sử q đúng, tức là a2 = b2 , suy ra a4 = a2 .a2 = b2 .b2 = b4 , tức là ta có p đúng, mệnh đề kéo theo thứ hai được chứng minh. Vì cả hai mệnh đề p → q và q → p đã được chứng minh là đúng nên mệnh đề tương đương với chúng p ↔ q là đúng. • Chứng minh tồn tại Nhiều định lý là các khẳng định sự tồn tại của các đối tượng thuộc một loại nào đó. Một định lý loại này là mệnh đề có dạng ∃xP (x) với P là vị ngữ. Chứng minh mệnh đề dạng ∃xP (x) gọi là chứng minh tồn tại. Có nhiều cách chứng minh định lý loại này. Đôi khi một chứng minh tồn tại của mệnh đề ∃xP (x) được hoàn tất bằng cách tìm một phần tử a sao cho P (a) đúng. Cách chứng minh tồn tại như vậy gọi là chứng minh tồn tại kiến thiết. Có cách chứng minh khác gọi là tồn tại không kiến thiết, tức là chúng ta không chỉ ra phần tử a sao cho P (a) đúng mà chứng minh rằng ∃xP (x) đúng bằng một cách khác. Ví dụ 1.12. Chứng minh rằng với mọi số nguyên dương n tồn tại n số nguyên dương liên tiếp đều là hợp số. Lời giải :Điều phải chứng minh tương đương với lượng hóa ∀n∃x∀(i = 1, n)(x + i) là hợp số. Với mọi n nguyên dương ta đặt x = (n + 1)! + 1. Khi đó x + i = (n + 1)! + (i + 1) chia hết cho (i + 1) với mọi i = 1, n. Vì vậy x + 1, x + 2, · · · , x + n là n hợp số liên tiếp. Trong cách chứng minh này ta đã chỉ ra số x để cho P (x) đúng. Đó là cách chứng minh tồn tại kiến thiết Thang Long University Library
11 •Phản ví dụ Giả sử mênh đề ∀xP (x) là sai. Chúng ta chứng tỏ điều này bằng cách nào? Nhớ lại rằng các mệnh đề ¬∀xP (x) và ∃x¬P (x) là tương đương. Điều này có nghĩa là nếu ta tìm được một phần tử a sao cho P (a) sai thì chúng ta chỉ ra được ∃x¬P (x) là đúng hay ∀xP (x) là sai. Phần tử a sao cho P (a) sai gọi là một phản ví dụ. Nếu tìm được chỉ một phản vi dụ cũng đủ chứng tỏ ∀xP (x) là sai. Ví dụ 1.13. Chứng tỏ rằng khẳng định “ Tất cả các số nguyên tố đều lẻ ” là sai. Lời giải: Mệnh đề “tất cả các số nguyên tố đều lẻ ” là một lượng hóa phổ dụng, tức là ∀xP (x), trong đó P (x) là mệnh đề “ x là lẻ ” và không gian đang xét là tập số nguyên tố. Chú ý rằng x = 2 là một phản ví dụ, vì 2 là số nguyên tố nhưng là số chẵn. Vì thế mệnh đề “ Tất cả các số nguyên tố đều lẻ ” là sai. 1.1..3 Phương pháp chứng minh quy nạp Toán học 1. Cơ sở phương pháp chứng minh quy nạp Toán học Phương pháp quy nạp Toán học là một phương pháp chứng minh Toán học đặc biệt, cho phép ta rút ra quy luật tổng quát trên cơ sở những trường hợp riêng. a, Tính sắp thứ tự tốt của tập N các số tự nhiên Tiên đề 1.1. Mọi tập không rỗng của tập các số tự nhiên N luôn có số bé nhất Định lý 1.1. A ⊂ N. Nếu 0 ∈ A và a ∈ A suy ra a + 1 ∈ A thì A = N Chứng minh: Giả sử A 6= N khi đó M = NA 6= ∅ ⇒M 6= ∅. Theo tiên đề trên M có số bé nhất là m0 , tức là tồn tại m0 ∈ M sao cho với mọi m ∈ M ta có m0 ≤ m. Vì m0 ∈ M nên m0 ∈ / A, do đó m0 6= 0. Vì m0 là số tự nhiên khác 0
12 nên a = m0 − 1 cũng là một số tự nhiên. Vì a < m0 nên a ∈ / M , suy ra a ∈ A. Theo giả thiết a + 1 ∈ A. Nhưng a + 1 = m0 . Vậy m0 ∈ A. Trên đây ta có m0 ∈ / A. Mâu thuẫn này chứng tỏ A = N b, Phương pháp chứng minh quy nạp Định lý 1.2. Cho P(n) là một hàm mệnh đề xác định trên tập các số tự nhiên N. Nếu P(0) đúng và ∀a ∈ N, P (a) −→ P (a+1) đúng ∀nP (n) đúng. Chứng minh: Đặt A = n0 ∈ N|P (n0 ) đúng là miền đúng của P (n). Khi đó ta có A = N. Thật vậy, P (0) đúng nên 0 ∈ A. Giả sử a ∈ A, khi đó P (a) đúng, theo giả thiết suy ra P (a + 1) đúng, do đó a + 1 ∈ A theo định lí 1.1 ta có A = N. Vì A = N nên ∀nP(n) đúng. Định lý 1.3. Cho P(n) là một hàm mệnh đề xác định trên N. Nếu P(n0 ) đúng và P (a)đúng, a ≥ n0 suy ra P (a + 1) đúng thì ∀n ≥ n0 , P (n) đúng. Chứng minh: Đặt A = 0, 1, ..., n0 − 1 ∪ EP (n) , trong đó EP (n) là miền đúng của P (n) rồi chứng minh giống như chứng minh trong định lí 1.2 ta có A = N. Suy ra với mọi x0 ≥ n0 ,x0 ∈ EP (n) suy ra P (x0 ) đúng. 2. Một số hình thức của phương pháp quy nạp Toán học • Phương pháp quy nạp thứ nhất [p(k0 ); ∀k ≥ k0 ; p(k) ⇒ p(k + 1)] ⇒ ∀n ≥ k0 , p(n) (1.1) Ví dụ 1.14. Với số tự nhiên a, số nguyên tố P.Chứng minh ap − a chia hết cho p (định lý nhỏ Fermat) Chứng minh Do không rõ quy luật phân bố của số nguyên tố p nên ta quy nạp theo a: a = 0 ⇒0p − 0 chia hết cho p. a = 1⇒1p − 1 chia hết cho p. Giả sử ap − a chia hết cho p với số tự nhiên a ≥ 0 Ta chứng minh (a + 1)p − (a + 1) chia hết cho p. Thang Long University Library
13 Khai triển: (a + 1)p = ap + 1 + Cp p−1 ap−1 + Cp p−2 ap−2 + ... + Cp 2 a2 + Cp 1 a Nhận xét rằng : kCp k = pCp−1 k−1 = bội số của p, Nhưng ∀k 2n + 5 Chứng minh Với n = 1 : 21+2 > 2.1 + 5: bất đẳng thức đúng. Giả sử bất đẳng thức đúng với n = k ≥ 1 : 2k+2 > 2k + 5 ta chứng minh nó cũng đúng với n = k + 1: 2(k+1)+2 = 2.2k+2 > 2(2k + 5) = 4k + 10 > 2k + 7 = 2(k + 1) + 5 Vậy bất đẳng thức đúng với n nguyên dương ta gọi hình thức quy nạp theo mệnh đề (1.1) là hình thức quy nạp chuẩn tắc. • Phương pháp quy nạp thứ hai [p(k0 ); ∀k − 1 ≥ k0 ; p(k − 1) ⇒ p(k)] ⇒ ∀n ≥ k0 , p(n) (1.2) Ví dụ 1.16. Chứng minh rằng nếu sin a 6= 0thì : sin 2n+1 a cos a. cos 2a. cos 4a... cos 2n a = n+1 2 sin a Chứng minh sin 2a n = 0 : cos a = 2 sin a Biểu thức đúng. Giả sử biểu thức đúng với n = k − 1(k > 0) ta chứng minh biểu thức đúng với n = k . Thật vậy:
14 sin 2k a. cos 2k a cos a. cos 2a... cos 2k−1 a. cos 2k a = 2k sin a sin 2k+1 a sin 2k+1 a = = 2.2k sin a 2k+1 sin a Tuy nhiên hình thức quy nạp lùi không phải lúc nào cũng thực hiện được, nhất la khi đối tượng lấy làm quy nạp là số mũ, vì lúc đó xuất hiện số mũ âm gây khó khăn khi tính toán. • Phương pháp quy nạp thứ ba [p(k0 ), p(k0 + 1), ...p(k0 + a − 1); ∀k ≥ k0 ; p(k) ⇒ p(k + a)] ⇒ ∀n ≥ k0 , p(n) Ví dụ 1.17. Tìm các số tự nhiên s để phương trình: 1 1 1 + + ... + =1 x1 2 x2 2 xs 2 Lời giải Khi s = 1, phương trình có nghiệm x = 1 Khi s = 2, giả sử phương trình có nghiệm (a1 ; a2 ; a1 ≤ a2 ), 1 1 1 1 1 1 2 ta có 2 ≥ 2 ⇒ 2 + 2 = 1 ≤ 2 + 2 = 2 a1 a2 a1 a2 a1 a1 a1 2 ⇒a1 ≤ 2 ⇒a1 = 1: vô lý Vậy với s = 2 phương trình vô nghiệm. Khi s = 4 thì (2; 2; 2; 2) là nghiệm của phương trình Khi s = 5, chứng minh tương tự như khi s = 3 và bằng phép thế ta biết phương trình vô nghiệm. √ √ √ Nói chung khi s chính phương thì phương trình luôn có nghiệm ( s; s; ...; s) Khi s = 6, 7, 8 phương trình có nghiệm tương ứng là (2; 2; 2; 3; 3; 6), (2; 2; 2; 4; 4; 4; 4), (3; 3; 3; 3; 3; 7; 14; 21) Giả sử với số tự nhiên s nào đó, phương trình có nghiệm: 1 1 1 2 + 2 + ... + 2 = 1 a1 a2 as Thang Long University Library