QUY NẠP TOÁN HỌC: phương pháp và các bài toán

Chia sẻ: Trần Văn Luân | Ngày: | Loại File: PDF | Số trang:26

Thêm vào BST

Báo xấu

181
lượt xem 35
download

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

Phương pháp quy nạp toán học là một phương pháp hay và rất hữu dụng. Tuy nhiên, đối với học sinh khối 11 thì đây là nội dung khó hiểu và khó áp dụng. Bài viết này của tôi sẽ giúp các bạn một hướng để hiểu hơn về phương pháp này.

Chủ đề:

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

Lưu

Nội dung Text: QUY NẠP TOÁN HỌC: phương pháp và các bài toán

1 B GIÁO D C VÀ ĐÀO T O Đ I H C ĐÀ N NG NGUY N TH THÙY DƯƠNG QUY N P TOÁN H C: PHƯƠNG PHÁP VÀ CÁC BÀI TOÁN CHUYÊN NGÀNH: PHƯƠNG PHÁP TOÁN SƠ C P MÃ S : 60.46.40 TÓM T T LU N VĂN TH C SĨ KHOA H C Đà N ng - Năm 2011
2 Công trình ñư c hoàn thành t i Đ I H C ĐÀ N NG Ngư i hư ng d n khoa h c: TS. NGUY N DUY THÁI SƠN Ph n bi n 1: PGS.TSKH.TR N QU C CHI N Ph n bi n 2: GS.TSKH. NGUY N VĂN M U Lu n văn ñư c b o v t i H i ñ ng b o v ch m Lu n văn t t nghi p Th c sĩ Khoa h c Xã h i và nhân văn, h p t i Đ i h c Đà N ng vào ngày 23 tháng 10 năm 2011 Có th tìm hi u lu n văn t i: - Trung tâm Thông tin - H c li u - Đ i h c Đà N ng - Thư vi n trư ng Đ i h c Sư ph m - Đ i h c Đà N ng
3 M Đ U 1. Lý do ch n ñ tài Phương pháp quy n p toán h c là m t trong nh ng hình th c suy lu n, hơn n a, là m t phương pháp ch ng minh c ñi n trong toán h c (m t s s gia cho r ng phương pháp này ñã ñư c s d ng t trư c công nguyên b i Plato, Aristotle). Có th nói ñây là m t trong nh ng phương pháp ch ng minh cơ b n và hi u qu , do ñó vi c ñưa nó vào chương trình Toán trung h c ph thông là t t y u. Bên c nh ñó, vi c th c hi n các bư c ch ng minh quy n p còn giúp h c sinh phát tri n năng l c trí tu (t ng h p, khái quát hóa). H c sinh gi i có th bi t phương pháp quy n p toán h c ngay t khi còn h c các l p trung h c cơ s , nhưng nói chung thì ph i ñ i ñ n năm h c l p 11 các em m i ñư c làm quen l n ñ u v i phương pháp ñó (qua sách giáo khoa Đ i s và Gi i tích). Và ch v i m t th i lư ng khá khiêm t n trong chương trình toán l p 11 (lư ng bài t p cũng h t s c ít i), nói chung ki n th c và k năng ch ng minh quy n p c a h c sinh thư ng là còn h n ch . T nh ng lý do ñó, chúng tôi ch n ñ tài “Quy n p toán h c: phương pháp và các bài toán” v i mong mu n nghiên c u, tích lũy nh ng ki n th c c n thi t cho vi c gi ng d y, ñ c bi t là vi c gi ng d y các h c sinh khá, gi i. 2. M c ñích và nhi m v nghiên c u Phương pháp quy n p mà các em h c trung h c ph thông thư ng ch là phương pháp có d ng c ñi n như sau. Đ ch ng minh m t “m nh ñ ch a bi n” P(n) là ñúng v i m i n ∈ * ta ti n hành hai bư c: Bư c 1. Ch ra r ng m nh ñ P(1) ñúng. Bư c 2. V i m i k ∈ * , ta ch ng minh r ng n u m nh ñ P(k) ñúng thì m nh ñ P(k + 1) cũng ñúng. Trong trư ng h p ph i ch ng minh r ng P(n) là ñúng v i m i s nguyên dương n ≥ m (m là m t s nguyên dương ñã cho) thì bư c 1 ta c n ki m tra m nh ñ P(m) ñúng và gi nguyên bư c 2 (nhưng v i k ≥ m). Th t ra, phương pháp quy n p toán h c có nhi u bi n th r t hay. M t trong các bi n th ñó ngày nay ñư c bi t ñ n dư i tên g i Quy n p (lùi) ki u Cauchy, do chính Cauchy s d ng l n ñ u khi ch ng minh b t ñ ng th c trung bình c ng – trung bình nhân: a1 + a2 + K + an n ≥ a1a2 L an (*) n
4 v i m i s nguyên dương n ≥ 2 và v i m i b n s th c không âm a1, a2, …, an. V i n = 2, (*) ñư c ch ng minh tr c ti p (ch dùng ki n th c trung h c cơ s ). V i n t ng quát, Cauchy ch ng minh r ng n u (*) ñã ñúng v i n = k (trong ñó, 2 ≤ k ∈ * ) thì (*) cũng ñúng khi n = 2k. B ng cách như v y, ta th y (*) ñúng v i m t dãy tăng vô h n các s nguyên dương n = 2m ( m ∈ * ). Cu i cùng, bư c m u ch t (thư ng ñư c g i là bư c lùi), Cauchy nh n xét r ng: n u (*) ñúng v i n = N ( N ∈ * , N > 2) thì nó cũng ñúng khi n = N − 1. Cách ch ng minh là khá ñơn gi n: v i a1, a2, …, aN-1 ≥ 0, xét a1 + a2 + K + aN −1 aN = (ho c aN = N −1 a1a2 L aN −1 ) N −1 và áp d ng (*) cho N s a1, a2, …, aN ≥ 0, ta có ngay b t ñ ng th c a1 + a2 + K + aN −1 N −1 ≥ a1a2 L an . N −1 T ñó suy ra (*) ñúng v i m i s nguyên dương n ≥ 2. Đ th y m t bi n th khác, trư c tiên chúng tôi xét m t bài toán khá khó (ñ i v i h c sinh gi i Toán trung h c ph thông): Bài toán (Pn). Ch ng minh r ng t 2n − 1 s nguyên b t kỳ ( n ∈ * ) ta luôn có th trích ra n s có t ng chia h t cho n. (Ph ng theo m t ñ thi ch n h c sinh gi i Toán Trung Qu c) Sơ lư c l i gi i c a bài toán (Pn): - Ch ng minh r ng n u k t lu n c a (Pn) và (Pm) là ñúng ( n, m ∈ * ) thì k t lu n c a (Pnm) cũng ñúng. - Ki m tra r ng k t lu n c a (Pn) là ñúng khi n là s nguyên t (ho c n = 1). Khi ñó, vì m i s nguyên dương l n hơn 1 ñ u có th phân tích thành tích c a các s nguyên t (ñ nh lí cơ b n c a s h c) ta th y k t lu n c a bài toán (Pn) ñúng cho m i s nguyên dương n. Chúng tôi g i phương pháp ñã dùng trên ñây khi gi i bài toán (Pn) là quy n p phân rã. Trong lu n văn này, chúng tôi trình bày các bi n th khác nhau c a phương pháp quy n p toán h c và ñ u tư không ít th i gian ñ tuy n ch n các bài toán (ñã t ng g p t i các kỳ thi) gi i ñư c b ng các phương pháp quy n p ñó. Sau m i l i gi i chúng tôi cũng thư ng có các nh n xét nh m nêu các hư ng gi i khác, t ng quát hóa ho c phân tích các sai sót mà h c sinh có th v p ph i. Chúng tôi hy v ng xây d ng nên m t tư li u h u ích, có th s d ng ñư c trong vi c gi ng d y h c sinh gi i các c p ñ khác nhau.
5 3. Đ i tư ng và ph m vi nghiên c u 3.1 Đ i tư ng nghiên c u: Quy n p toán h c và các bài toán liên quan. 3.2 Ph m vi nghiên c u: Các d ng toán s d ng phương pháp quy n p toán h c. 4. Phương pháp nghiên c u Cơ b n s d ng phương pháp nghiên c u tài li u (sách, báo và các tài li u trên internet có liên quan ñ n ñ tài c a lu n văn) ñ thu th p thông tin và trình bày l i theo m t th khép kín; t p h p các d ng toán ph c v cho yêu c u c a ñ tài, tìm hi u cách gi i và phân lo i. 5. Ý nghĩa khoa h c và th c ti n c a ñ tài Xây d ng m t giáo trình có tính h th ng, khép kín và có th gi ng d y ñư c cho các h c sinh chuyên toán b c trung h c ph thông. Xây d ng ñư c m t h th ng các bài toán (cũ và m i) v i các m c ñ khó d khác nhau. 6. C u trúc lu n văn Lu n văn này ñư c chia làm ba chương. Chương 1. Quy n p toán h c, nguyên lý s p th t t t. Trong chương này, chúng tôi trình bày h tiên ñ Peano, m t s d ng c a nguyên lý quy n p toán h c và nguyên lý s p th t t t trên t p các s nguyên dương. Cu i chương là m t tuy n ch n các bài toán áp d ng. Chương 2. M t s bi n th c a phép quy n p. Trong chương này, chúng ta g p các bi n th khác nhau c a phép quy n p, ñ c bi t là quy n p lùi (quy n p ki u Cauchy), quy n p phân rã và các ví d áp d ng. Chương 3. Quy n p siêu h n. Chương cu i này gi i thi u t ng quan v t p ñư c s p th t tuy n tính, ki u th t ; t p ñư c s p th t t t, s th t ; ñ nh lý v phép quy n p siêu h n, dãy siêu h n.
6 CHƯƠNG 1. QUY N P TOÁN H C, NGUYÊN LÝ S P TH T T T 1.1 CÁCH TI P C N TIÊN Đ Đ I V I CÁC S T NHIÊN, NGUYÊN LÝ QUY N P Các s nguyên dương có th ñư c trình bày b ng phương pháp tiên ñ như sau. Các khái ni m ñư c ch p nh n (là nguyên th y) g m có b n thân t p *, s 1 và khái ni m “s ti p sau” c a m t s nguyên dương. Nói nôm na, ý nghĩa quy n p c a khái ni m ñó n m ch : m là s ti p sau c a n n u m là s nguyên dương tr c ti p theo sau s nguyên dương n . Như v y, 2 là s ti p sau c a 1 , 3 là s ti p sau c a 2 , v. v... Các tiên ñ sau ñây h p thành h tiên ñ cho các s nguyên dương. Tiên ñ I: 1 là m t s nguyên dương, t c là 1 ∈ *. Tiên ñ II: 1 không ph i là s ti p sau c a b t kỳ m t s nguyên dương nào. Tiên ñ III: Đ i v i m i s nguyên dương n có ñúng m t s nguyên dương m sao cho m là s ti p sau c a n . Tiên ñ IV: N u m t s nguyên dương m là s ti p sau c a m t s nguyên dương n và n u m cũng là s ti p sau c a m t s nguyên dương k thì n = k . Tiên ñ V (Nguyên lý quy n p): N u A là m t t p h p con c a t p h p * các s nguyên dương sao cho: 1 ∈ A, (1.1) và ñ i v i m i s nguyên dương n : n u n ∈ A và m là s ti p sau c a n thì m ∈ A, (1.2) thì m i s nguyên dương ñ u thu c A, t c là A = *. H tiên ñ trên do Peano ñưa ra vào năm 1891. H tiên ñ ñó là ñ ñ xây d ng t t c các ñ nh lý c a s h c trên các s nguyên dương. M i khái ni m khác dùng trong s h c các s nguyên dương như phép tính c ng và phép tính nhân, quan h “nh hơn” v.v... ñ u có th ñư c ñ nh nghĩa thông qua nh ng ñi u ñã ñư c ch p nh n trong h tiên ñ ñó. Bây gi chúng ta xét xem phép c ng và phép nhân các s nguyên dương có th ñ nh nghĩa ñư c như th nào thông qua h tiên ñ Peano. Theo tiên ñ III, ñ i v i m i s nguyên dương n có ñúng m t s nguyên dương m sao cho m là s ti p sau c a n . Ký hi u s ti p sau c a n là n ' . Phép c ng các s nguyên dương ñư c ñ nh nghĩa b i: n + 1 = n ' v i m i n ∈ *, (1.3) n + m ' = (n + m) ' v i m i n ∈ * và m ∈ *. (1.4)
7 Hai công th c này t o thành ñ nh nghĩa quy n p c a phép c ng các s nguyên dương. Ta s ch ng minh r ng ñ i v i m i m t c p các s nguyên dương n, m thì t ng n + m c a chúng ñư c xác ñ nh b ng cách này. G i n là m t s nguyên dương b t kỳ và A là t p h p các s nguyên dương m mà t ng n + m ñư c xác ñ nh. Do (1.3) t ng n + 1 ñư c xác ñ nh và do ñó 1 ∈ A . Bây gi gi s m ∈ A , t c là t ng n + m ñư c xác ñ nh. Do (1.4) t ng n + m ' cũng ñư c xác ñ nh nên m ' ∈ A . Như v y gi thi t (1.1) và (1.2) c a nguyên lý quy n p ñư c th a mãn ñ i v i t p h p A . Theo nguyên lý này m i s nguyên dương là thu c A và do ñó t ng n + m ñư c xác ñ nh ñ i v i m i s nguyên dương m . Vì trong ch ng minh trên, n ∈ * là b t kỳ nên t ng n + m ñư c xác ñ nh ñ i v i m i c p n, m các s nguyên dương. H sau ñây cho ta m t ñ nh nghĩa quy n p c a phép nhân các s nguyên dương: n ⋅1 = n v i m i n ∈ * (1.5) n ⋅ m ' = ( n ⋅ m ) + n v i m i n, m ∈ * . (1.6) Ta s ch ng minh r ng tích n ⋅ m ñư c xác ñ nh ñ i v i m i c p các s nguyên dương n, m . G i n là m t s nguyên dương b t kỳ và A là t p h p t t c các s nguyên dương m mà tích n ⋅ m ñư c xác ñ nh. Do (1.5), tích n ⋅1 ñư c xác ñ nh và vì v y 1 ∈ A . N u m ∈ A , t c là n ⋅ m ñư c xác ñ nh thì theo (1.6) tích n ⋅ m ' cũng ñư c xác ñ nh, t c là m ' ∈ A . Như v y các gi thi t c a nguyên lý quy n p ñư c th a mãn b i t p h p A . V y ta k t lu n r ng m i s nguyên dương là thu c A , t c là tích n ⋅ m ñư c xác ñ nh ñ i v i m i c p n, m các s nguyên dương. Qu n h “nh hơn” ñ i v i các s nguyên dương có th ñư c xác ñ nh nh phép c ng như sau: n < m khi và ch khi có m t s nguyên dương k sao cho m + k = n. (1.7) Quan h “nh hơn ho c b ng” ñư c ñ nh nghĩa sau ñó m t cách hi n nhiên. Khi ñã có phép c ng trên t p h p các s nguyên dương, ta có th phát bi u l i tiên ñ V dư i d ng (thư ng hay ñư c s d ng nh t): Đ nh lý 1.1.1 (Nguyên lý quy n p toán h c) Gi s P là m t tính ch t ñư c xác ñ nh trên t p h p t t c các s nguyên dương sao cho P (1) ( 1 có tính ch t P) (1.8) và ñ i v i m i s nguyên dương n , n u P (n) thì P (n + 1) (n u n có tính ch t P thì n + 1 cũng có tính ch t P). (1.9)
8 Khi ñó, m i s nguyên dương ñ u có tính ch t P. Dùng nguyên lý quy n p ta cũng ch ng minh ñư c: Đ nh lý 1.1.2 (Nguyên lý s p th t t t) Trong m i t p h p không r ng các s nguyên dương có m t s nh nh t, t c là m t s nh hơn m i s khác trong t p h p. Đ nh lý 1.1.3 Gi s A là m t t p h p con c a t p h p t t c các s nguyên dương sao cho 1∈ A (1.10) và v i m i s nguyên dương n , n u k ∈ A ñ i v i t t c các s nguyên dương k ≤ n thì n + 1 ∈ A . (1.11) Khi ñó, m i s nguyên dương ñ u thu c A , t c là A = *. Nh n xét 1.1.1 Nguyên lý quy n p toán h c d ng tiên ñ V là m t h qu logic c a ñ nh lý 1.1.3. Đ ch ng minh ñi u này, ta gi s r ng ñ nh lý 1.1.3 là ñúng và A là m t t p h p con b t kỳ c a * th a mãn các ñi u ki n (1.1) và (1.2) trong tiên ñ V. Đi u ki n (1.1) trùng v i ñi u ki n (1.10). N u ñi u ki n (1.2) ñư c th a mãn thì ñi u ki n (1.11) t t nhiên cũng ñư c th a mãn. Vì v y, áp d ng ñ nh lý 1.1.3 ta k t lu n r ng m i s nguyên dương ñ u thu c A . Do ñó, ñ nh lý 1.1.3 kéo theo tiên ñ V. Đ nh lý sau ñây cũng thư ng ñư c áp d ng khi ch ng minh quy n p. Đ nh lý 1.1.4 Gi s A là m t t p h p con c a t p h p * t t c các s nguyên dương sao cho 1 ∈ A và 2 ∈ A (1.12) và v i m i s nguyên dương n > 1, n u n − 1 ∈ A và n ∈ A thì n + 1 ∈ A . (1.13) Khi ñó, m i s nguyên dương ñ u thu c A . Đ nh lý 1.1.5 Gi s P (n) là m t hàm m nh ñ c a bi n n bi n thiên trên t p h p * t t c các s nguyên dương sao cho P (1) ñúng (1.14) và v i m i s nguyên dương n , n u P (k ) ñúng ñ i v i m i s nguyên dương k ≤ n thì P (n + 1) cũng ñúng. (1.15)
9 Khi ñó, P (n) ñúng ñ i v i m i s nguyên dương n. Tiên ñ V và ñ nh lý 1.1.4 cũng có th ñư c phát bi u l i m t cách tương t . C n chú ý r ng: khi làm vi c v i các s t nhiên (thay vì các s nguyên dương), (1.8) và (1.14) ta xét P(0) thay cho P(1). Đ ch ng minh m t “m nh ñ ch a bi n” P(n) là ñúng v i m i s t nhiên n ≥ m (m là m t s t nhiên ñã cho), ta ti n hành hai bư c: Bư c 1 (thư ng ñư c g i là bư c cơ s ). Ch ra r ng m nh ñ P(m) ñúng. Bư c 2 (bư c quy n p). V i m i s t nhiên k ≥ m, ta ch ng minh r ng n u m nh ñ P(k) ñúng thì m nh ñ P(k + 1) cũng ñúng. 1.2. CÁC VÍ D ÁP D NG Cách ch ng minh m t ñ nh lý toán h c có dùng ñ n nguyên lý quy n p toán h c thư ng ñư c g i là phép quy n p. Các ví d v nh ng cách ch ng minh này áp d ng cho các bài toán t h p s ñư c trình bày dư i ñây: Ví d 1.2.1 V i m i s t nhiên n , s t p h p con c a m i t p h p g m n ph n t là 2n . Ví d 1.2.2 Đ i v i m i c p s t nhiên n, k mà k ≤ n, s t h p ch p k l y t n ph n n t (c a m t t p h p An cho trư c) b ng   . k  Ví d 1.2.3 Cho a và b là hai s th c phân bi t có t ng là m t s dương. Ch ng minh r ng 2n −1 (a n + b n ) > (a + b)n (1.22) v i m i s t nhiên n > 1. Ví d 1.2.4 Cho a ≥ b > 0. Ch ng minh r ng (n − 1)a n + b n ≥ na n −1b (1.26) v i m i s nguyên dương n; hơn n a, d u ñ ng th c x y ra trong (1.26) khi và ch khi a = b ho c n = 1. Ví d 1.2.5 V i m i s nguyên dương n, ký hi u Rn = 2 + 2 + 2 + ... + 2 . Ch ng minh r ng 1444 24444 4 3 n dÊu c¨n π 1 π 1 cos n = Rn −1 , sin n = 2 − Rn − 2 (1.28) 2 2 2 2 khi n ≥ 3.
10 Nh n xét 1.2.1 Th t ra, n u ta quy ư c R0 := 0 (ñ công th c truy h i Rn = 2 + Rn −1 còn có hi u π 1 π 1 l c khi n = 1), thì v n có: sin = 2 − Rn − 2 khi n = 2, cos n = Rn −1 khi n ∈ {1;2}. 2n 2 2 2 Ví d 1.2.6 V i m i s t nhiên n ≥ 2, ta có b t ñ ng th c: 4n (2n)! < ⋅ (1.29) n + 1 (n !) 2 Ví d 1.2.7 (IMO 1957) Cho hàm s f : * → * th a ñi u ki n: f ( n + 1) > f ( f ( n ) ) v i m i n ∈ * . (1.31) Ch ng minh r ng f ( n ) = n v i m i n∈ * . Nh n xét 1.2.2 Sau khi ñã ch ng minh ñư c d1 = min A1 = f (1) , d 2 = min A2 = f ( 2 ) , ta có th ti p t c l i gi i theo m t hư ng khác như sau: N u f (1) ≥ 2 thì f ( f (1) ) ∈ A2 ⇒ f ( f (1) ) ≥ d 2 = f ( 2 ) , mâu thu n v i (1.7). V y f (1) = 1 . D th y hàm g : *→ * cho b i công th c g ( n ) = f ( n + 1) − 1 cũng th a mãn g ( g ( n ) ) < g ( n + 1) . Theo ch ng minh trên, ta có g (1) = 1 ⇒ f ( 2 ) = 2 . B ng cách như v y, ta có f ( n ) = n v i m i n ∈ * . Ví d 1.2.8 Tìm t t c các hàm s f: → th a mãn ñi u ki n: mf (n) + nf (m) = (m + n) f (m 2 + n 2 ) (1.32) v i m i m, n ∈ . Nh n xét 1.2.3 Ta có th gi i bài toán theo cách khác (không dùng nguyên lý s p th t t t): Sau khi ñã ch ng minh ñư c (1.33), ñ t g (n) := f (n) − f (0) (∀n ∈ ), ta th y hàm s g : → th a mãn ñi u ki n: mg (n) + ng (m) = ( m + n) g (m 2 + n 2 ) (1.32’) và g (m 2 ) = 0 (1.33’) v i m i m, n ∈ . Trong (1.32’), ch n m = n, ta ñư c
11 g (m) = g (2m 2 ) (1.34) (v i m i m ∈ * và do ñó) v i m i m ∈ . L y m = k 2 , n = 2k 2 và dùng (1.33’), (1.34), ta th y: (1.32') ⇒ k 2 g ( k ) = 3k 2 g (5k 4 ) ⇒ g (k ) = 3 g (5k 4 ) (1.35) v i m i k ∈ *. Theo (1.33’), g (0) = 0 nên (1.35) còn ñúng v i m i k ∈ .  4 −1  n T ñó, b ng quy n p, ta có: g (k ) = 3 g  5 3 k 4  M 3n v i m i s t nhiên n. n n   Suy ra: g (k ) = 0 v i m i s t nhiên k; t c là, hàm s f h ng trên (kh p) . Th l i!
12 CHƯƠNG 2. M T S BI N TH C A PHÉP QUY N P 2.1 QUY N P LÙI Phép quy n p có nhi u bi n th r t hay. M t trong các bi n th ñó ngày nay ñư c bi t ñ n dư i tên g i “quy n p lùi” (còn ñư c g i là “quy n p ki u Cauchy”), do chính Cauchy s d ng l n ñ u khi ch ng minh b t ñ ng th c trung bình c ng – trung bình nhân: a1 + a2 + K + an n ≥ a1a2 L an (2.1) n v i m i s nguyên dương n ≥ 2 và v i m i b n s th c không âm a1, a2, …, an. V i n = 2, (2.1) ñư c ch ng minh tr c ti p (ch dùng ki n th c trung h c cơ s ). V i n t ng quát, Cauchy ch ng minh r ng n u (2.1) ñã ñúng v i n = k (trong ñó, 2 ≤ k ∈ * ) thì (2.1) cũng ñúng khi n = 2k. B ng cách như v y, ta th y (2.1) ñúng v i m t dãy tăng vô h n các s nguyên dương n = 2m ( m ∈ * ). Cu i cùng, bư c m u ch t (thư ng ñư c g i là bư c lùi), Cauchy nh n xét r ng: n u (2.1) ñúng v i n = N ( N ∈ * , N > 2) thì nó cũng ñúng khi n = N − 1. Cách ch ng minh cũng khá ñơn gi n (nhưng tinh t ): v i a1, a2, …, aN-1 ≥ 0, xét a1 + a2 + K + aN −1 aN = (ho c aN = N −1 a1a2 L aN −1 ) N −1 và áp d ng (2.1) cho N s a1, a2, …, aN ≥ 0, ta có ngay b t ñ ng th c a1 + a2 + K + aN −1 N −1 ≥ a1a2 L an . N −1 T ñó suy ra (2.1) ñúng v i m i s nguyên dương n ≥ 2. Ta có th t ng quát hóa ý tư ng c a Cauchy thành: Đ nh lý 2.1.1 (Nguyên lý quy n p lùi) Cho (mk )∞=1 là m t dãy vô h n các s nguyên dương mà lim mk = ∞. Gi s k k →∞ P (n) là m t hàm m nh ñ c a bi n n bi n thiên trên t p h p * t t c các s nguyên dương sao cho P (mk ) ñúng (2.2) v i m i k ∈ *; hơn n a, v i m i s nguyên dương n > 1, n u P (n) ñúng thì P (n − 1) cũng ñúng. (2.3) Khi ñó, P (n) ñúng ñ i v i m i s nguyên dương n.
13 Ví d 2.1.1 Dùng phương pháp quy n p lùi, ch ng minh r ng n 1 n ∑1+ x n ≤ n (2.4) i =1 i 1 + ∏ xi i =1 v i m i dãy s h u h n ( xi )i =1 ⊂ [ 0, 1] (2 ≤ n ∈ ). n Nh n xét 2.1.2 Có th dùng b t ñ ng th c Jensen: 1 n 1 n  ∑ f (ti ) ≤ f  ∑ ti  n i =1  n i =1  1 ñ i v i hàm s y = f (t ) := liên t c và “lõm” trên n a kho ng −∞ < t ≤ 0, r i 1 + e nt ñ i bi n ti := ln xi (∀i ) ñ có m t cách ch ng minh khác cho (2.4) trong trư ng n h p ( xi )in=1 ⊂ ( 0,1]. Trư ng h p ∏ xi = 0, (2.4) ñúng m t cách hi n nhiên! i =1 Ví d 2.1.2 Dùng phương pháp quy n p lùi, ch ng minh r ng n 1 n ∑ 1 + xk n ≤ n (2.6) 1 + ∏ xk k =1 k =1 v i m i dãy s h u h n ( xi )i =1 ⊂ [ 0, 1] (2 ≤ n ∈ ). n 2.2. QUY N P PHÂN RÃ Đ th y m t bi n th khác, trư c tiên chúng tôi xét m t bài toán khá khó (ñ i v i h c sinh gi i Toán trung h c ph thông): Bài toán (Pn). Ch ng minh r ng t 2n − 1 s nguyên b t kỳ ( n ∈ * ) ta luôn có th trích ra n s có t ng chia h t cho n. (Ph ng theo m t ñ thi ch n h c sinh gi i Toán Trung Qu c) L i gi i c a bài toán (Pn) s ñư c trình bày qua các bư c như sau (xem các b ñ 2.2.1-2.2.2): - Ch ng minh r ng n u k t lu n c a (Pn) và (Pm) là ñúng ( n, m ∈ * ) thì k t lu n c a (Pnm) cũng ñúng. - Ki m tra r ng k t lu n c a (Pn) là ñúng khi n là s nguyên t (ho c n = 1). T ñó ta s th y k t lu n c a bài toán (Pn) ñúng cho m i s nguyên dương n. Chúng tôi m o mu i g i phương pháp làm này là phép quy n p phân rã. Và th c s , ta có:
14 Đ nh lý 2.2.1 (Nguyên lý quy n p phân rã) Gi s P(n) là m t hàm m nh ñ c a bi n n bi n thiên trên t p h p * t t c các s nguyên dương sao cho P (1) và P ( p ) ñúng (2.9) v i s nguyên t p; hơn n a, v i m i c p s nguyên dương m và n, n u P(m) và P(n) ñ u ñúng thì P(mn) cũng ñúng. (2.10) Khi ñó, P(n) ñúng ñ i v i m i s nguyên dương n. B ñ 2.2.1 N u k t lu n c a (Pn) và (Pm) là ñúng ( n, m ∈ * ) thì k t lu n c a (Pnm) cũng ñúng. B ñ 2.2.1 K t lu n c a (Pn) là ñúng khi n là s nguyên t ho c n = 1. Ví d 2.2.1 V i m i c p s nguyên dương a, m mà m > 1, ta ñ u có: a m ≡ a m−ϕ ( m ) (mod m); (2.15) trong ñó, ϕ(m) là s s nguyên dương nguyên t cùng nhau v i m và không vư t quá m (phi-hàm Euler). 2.3. M T S VÍ D V CÁC BI N TH KHÁC C A PHÉP QUY N P Trong m c này ta xét thêm m t s bi n th khác c a phép quy n p thông qua các ví d c th . Ví d 2.3.1 Tìm t t c các hàm f : * → * th a mãn ñ ng th i các ñi u ki n: (a) f (2) = 2 ; (b) f (mn) = f (m) f (n) v i m i m, n ∈ * ; (c) f (m) < f (n) v i m i m < n. Ví d 2.3.2 Tìm t t c các hàm f : * → * th a mãn ñ ng th i các ñi u ki n: (a) f (2) = 2 ; (b) f (mn) = f (m) f (n) v i m i s nguyên dương m, n nguyên t cùng nhau; (c) f (m) < f (n) v i m i m < n.
15 Nh n xét 2.3.1 Trong l i gi i trên, ñ bư c quy n p th c s “ti n lên”, b t ñ ng th c n 2 − n > n ⇔ n ( n − 2 ) > 0 ⇔ n ≥ 3 là r t c n thi t. Chính vì v y, bư c cơ s c n ki m tra ít nh t là v i 1 ≤ n ≤ 3; n u không, phép quy n p chưa thành công! CHƯƠNG 3. QUY N P SIÊU H N 3.1 T P ĐƯ C S P TH T TUY N TÍNH, KI U TH T 3.1.1 S p th t tuy n tính Cho t p h p X ñư c s p th t b i m t quan h hai ngôi ≤ . Quan h th t ñó ñư c g i là m t quan h th t tuy n tính n u nó th a mãn ñi u ki n liên thông sau ñây: x ≤ y ho c y ≤ x v i m i x, y ∈ X . (3.1) Như v y phép s p th t tuy n tính trên m t t p h p X (ñã ñư c cho trư c) là ph n x , b c c u, ph n ñ i x ng và liên thông trên X . N u quan h ≤ là m t quan h s p th t tuy n tính trên X thì ta nói r ng ≤ s p th t tuy n tính X và c p có th t ( X , ≤) ñư c g i là m t t p h p ñư c s p th t tuy n tính (hay m t xích). N u ( X , ≤) là m t t p h p ñư c s p th t tuy n tính thì ta nói r ng x ñ ng trư c y n u x ≤ y và x ≠ y; khi ñó, ta ký hi u x p y. B ng cách ñó, ta thu ñư c m t quan h hai ngôi p trên X mà ñi u ki n sau ñây ñư c th a mãn ñ i v i hai ph n t x, y b t kỳ c a X : n u x ≠ y thì x p y ho c y p x. (3.2) Đi u ki n này ñư c suy tr c ti p t (3.1) và t ñ nh nghĩa c a quan h p trên X . Ví d 3.1.1.1 Cho R0 là m t t p h p con b t kỳ c a t p h p t t c các s th c. Quan h “không l n hơn” ≤ trên R0 s p th t tuy n tính t p h p ñó. Tương t , quan h “không bé hơn” ≥ trên R0 s p th t t p h p ñó m t cách tuy n tính. Như v y, ( R0 , ≤) và ( R0 , ≥) là nh ng ví d v các t p h p ñư c s p th t tuy n tính, t c là các xích. Ví d 3.1.1.2 Cho là t p h p t t c các s ph c và ≤ là m t quan h hai ngôi trên ñư c xác ñ nh như sau: V i ( x1 , y1 ) và ( x2 , y2 ) b t kỳ trong . (( x1 , y1 ) ≤ ( x2 , y2 )) ⇔ (( x1 < x2 ) ∨ (( x1 = x2 ) ∧ ( y1 ≤ y2 ))) (3.3)
16 Do (3.3), quan h ≤ x y ra gi a hai s ph c ( x1 , y1 ) và ( x2 , y2 ) khi và ch khi ph n th c x1 c a s th nh t nh hơn ph n th c x2 c a s kia, ho c n u các ph n th c c a c hai s là b ng nhau thì ph n o y1 c a s th nh t không l n hơn ph n o y2 c a s kia . D dàng th l i ñư c quan h ≤ ñư c xác ñ nh như v y trên s p th t tuy n tính t p h p ñó. Như v y ( , ≤ ) là m t xích trong ñó là m t t p h p t t c các s ph c và ≤ là quan h trên ñư c xác ñ nh b i công th c (3.3). Ví d 3.1.1.3 Cho T là t p h p t t c các s th c, gi s r ng v i m i t ∈ T , Αt = { z ∈ : z < t} trong ñó là t p h p t t c các s ph c. Đi u này xác ñ nh m t h các ch s các t p h p con c a . Ta ñã bi t r ng h R t t c các t p h p Αt , t ∈ T là ñư c s p th t b i quan h bao hàm. D dàng th l i ñư c quan h bao hàm này trong h R s p th t tuy n tính R . Vì v y ( R, ⊂) là xích m t. Tuy nhiên c n ph i nh n m nh quan h bao hàm thư ng ch s p th t các h nh ng t p h p. Đ nh lý 3.1.1.1 N u ( X , ≤) là m t t p h p ñư c s p th t tuy n tính và n u A ⊂ X thì ( A, ≤ A) cũng là m t t p h p ñư c s p th t tuy n tính. M t ph n t x0 ∈ X c a m t t p h p ñư c s p th t tuy n tính ( X , ≤) ñư c g i là ph n t l n nh t n u x ≤ x0 v i m i x ∈ X (3.4) Thay cho “ph n t l n nh t” ta còn nói “ph n t sau cùng” Đ nh lý 3.1.1.2 V i m i ph n t x0 c a m t t p h p ñư c s p th t tuy n tính ( X , ≤), nh ng ñi u ki n sau ñây là tương ñương v i nhau: x0 là ph n t sau cùng (3.5) x p x0 v i m i x ∈ X \ { x0 } (3.6) x0 là m t ph n t c c ñ i, t c là ∨ (( x ≠ x ) ∧ ( x x∈ X 0 0 ≤ x)) (3.7) Đ nh lý 3.1.1.3 V i m i ph n t x0 c a m t t p h p ñư c s p th t tuy n tính ( X , ≤) thì nh ng ñi u ki n sau ñây là tương ñương x0 là ph n t ñ u tiên (3.9)
17 x0 p x v i m i x ∈ X \ { x0 } (3.10) x0 là m t ph n t c c ti u, t c là ∨ (( x ≠ x ) ∧ ( x ≤ x )) x∈ X 0 0 (3.11) Đ nh lý 3.1.1.4 N u ( X , ≤) là m t t p h p ñư c s p th t tuy n tính và n u X là m t t p h p h u h n không r ng thì ( X , ≤) có m t ph n t ñ u tiên và m t ph n t sau cùng. 3.1.2 Phép ñ ng c u c a các t p h p ñư c s p th t tuy n tính Hai t p h p ñư c s p th t tuy n tính ( X , ≤) và ( X *, ≤ *) ñư c g i là ñ ng d ng hay ñ ng c u và ñư c ký hi u b i công th c ( X , ≤) ( X *, ≤ *) n u có m t hàm m t ñ i m t f : X → X * ánh x X lên X * và cũng th a mãn ñi u ki n sau ñây ñ i v i b t kỳ x, y ∈ X x ≤ y khi và ch khi f ( x) ≤ * f ( y ) (3.12) Ví d 3.1.2.1 Cho là t p h p t t c các s nguyên, xét ( , ≤) trong ñó ≤ là quan h không l n hơn trên . Cũng cho là t p h p t t c các s nguyên và ≤ * là m t quan h trên ñư c xác ñ nh như sau: V i b t kỳ m, n ∈ , m ≤ *n khi và ch khi m là m t s ch n và n là m t s l , ho c n ≤ m và m, n ñ u là ch n, ho c m ≤ n và m, n ñ u là l . Quan h ≤ * s p th t tuy n tính và các t p h p ñư c s p th t tuy n ( , ≤) và ( , ≤ *) là ñ ng c u. Vì cho f : → là m t hàm ñư c xác ñ nh như sau: 2k + 1 khi k ≥ 0, k ∈ f (k ) =  −2k khi k < 0, k ∈ Hàm f : → là hàm m t ñ i m t và cũng th a mãn ñi u ki n v i các s nguyên b t kỳ m, n . (m ≤ n) ⇔ ( f (m) ≤ * f (n)) Đ nh lý 3.1.2.1 N u các t p h p ñư c s p th t tuy n tính và là ñ ng c u v i nhau thì các t p h p X và X * là tương ñương . Bây gi ta s ch ng minh ñi u ki n (3.12) có th ñư c thay th b ng m t ñi u ki n y u hơn, ñó là: Đ nh lý 3.1.2.2 Các t p h p ñư c s p th t tuy n tính ( X , ≤) và ( X *, ≤ *) là ñ ng c u v i nhau khi và ch khi có m t hàm m t ñ i m t f : X → X * ánh x X lên X * và cũng th a mãn ñi u ki n sau:
18 N u x ≤ y thì f ( x) ≤ * f ( y ) v i m i x, y ∈ X (3.13) Gi s r ng f : X → X * là hàm m t ñ i m t ánh x X lên X * và th a mãn ñi u ki n (3.13). Cũng gi s r ng công th c x ≤ y không ñúng ñ i v i m t vài ph n t x, y c a X . Đi u này và tính ph n x c a quan h ≤ cho x ≠ y. T nh ng ñi u ki n (3.1) ta cũng suy ra y ≤ x. Đi u này và (3.13) cho f ( y ) ≤ * f ( x) . Vì f là m t hàm m t ñ i m t và x ≠ y nên f ( y ) ≠ f ( x). Do ñó công th c f ( x) ≤ * f ( y ) không ñúng vì công th c này cùng v i f ( y ) ≤ * f ( x) s kéo theo f ( x) = f ( y ). Đi u này trái v i f ( y ) ≠ f ( x). Như v y ta ñã ch ng minh ñư c n u x ≤ y không ñúng thì f ( x) ≤ * f ( y ) cũng không ñúng. T ñi u ki n (3.13) kéo theo là ñi u ki n (3.12) ñư c th a mãn ñ i v i hàm f và ñ nh lý 3.1.2.2 ñã ñư c ch ng minh. Trong trư ng h p các t p h u h n thì ñ nh lý ñ o c a ñ nh lý 3.1.2.1 cũng ñúng Đ nh lý 3.1.2.3 N u ( X , ≤) và ( X *, ≤ *) là các t p h p h u h n ñư c s p tuy n tính và n u X = X * thì ( X , ≤) ( X *, ≤ *) . Đ nh lý 3.1.2.4 Các công th c sau ñây ñúng ñ i v i các xích b t kỳ ( X , ≤) , ( X *, ≤ *) và ( X ', ≤ ') ( X , ≤) ( X , ≤) (3.14) (( X , ≤) ( X *, ≤ *)) ⇒ (( X *, ≤ *) ( X , ≤)) (3.15) (( X , ≤) ( X *, ≤ *)) ∧ (( X *, ≤ *) ( X ', ≤ ')) ⇒ (( X , ≤) ( X ', ≤ ')) (3.16) Nh n xét 3.1.2.2 Theo ñ nh lý 3.1.2.3, hai t p h u h n ñư c s p th t tuy n tính mà cùng có n ph n t thì ñ ng c u v i nhau và vì v y chúng s cùng ki u th t . Ki u các t p h p h u h n ñư c s p th t tuy n tính mà ñ u có n ph n t s ñư c ký hi u là n . Ki u c a t p h p r ng ñư c ký hi u là ∅. Các ki u th t sau ñây c a các t p h p vô h n ñư c s p th t tuy n tính gi m t vai trò r t quan tr ng: Ki u t p h p t t c các s t nhiên, ñư c s p th t tuy n tính b i quan h “không l n hơn” (ký hi u là ω ), ki u t p h p các s nguyên âm ñư c s p th t tuy n tính b i quan h “không l n hơn” (ký hi u là ω * ), ki u t p h p t t c các s h u t ñư c s p th t tuy n tính b i quan h “không l n hơn” (ký hi u là η ), ki u t p h p t t c các s th c ñư c s p th t tuy n tính b i quan h “không l n hơn” (ký hi u là λ ). Chú ý r ng các t p h p ñư c s p th t tuy n tính ki u ω là ñ m ñư c, có m t ph n t th nh t và không có ph n t sau cùng, các t p h p ñư c s p th t tuy n tính ki u ω * là ñ m ñư c, có m t ph n t sau cùng và
19 không có ph n t th nh t, các t p h p ñư c s p th t tuy n tính ki u η là ñ m ñư c và không có ph n t th nh t cũng không có ph n t sau cùng, các t p h p ñư c s p th t tuy n tính ki u λ có l c lư ng continum và không có ph n t th nh t ho c không có ph n t sau cùng. 3.2 T P ĐƯ C S P TH T T T, S TH T 3.2.1 Quan h s p th t t t, s th t Cho t p h p X ñư c s p th t b i m t quan h hai ngôi ≤ . Quan h th t ñó xác l p m t s s p th t tuy n tính ñư c g i là s p t t n u nó th a mãn ñi u ki n: (w) v i m i t p h p con không r ng A c a t p h p X thì t p h p ñư c s p th t tuy n tính ( A, ≤ A) có m t ph n t ñ u tiên. N u ≤ là m t quan h ñư c s p t t trên X thì ta cũng nói r ng ≤ là s p th t t t X và c p ñư c s p th t ( X , ≤) ñư c g i là m t t p h p ñư c s p t t. Các ki u th t c a các t p h p ñư c s p th t t t ñư c g i là các s th t . Các s th t bao hàm ki u th t c a t p h p r ng thì ñư c ký hi u là 0. Ví d 3.2.1.2 T ñ nh lý 3.1.1.4 suy ra r ng n u ( X , ≤) là m t t p h p ñư c s p th t tuy n tính và n u X là m t t p h p không r ng h u h n thì ( X , ≤) ñư c s p th t t t. Như v y m i t p h p h u h n ñư c s p th t tuy n tính là ñư c s p th t t t. Ta ñã bi t (theo ñ nh lý 3.1.2.3) nh ng t p h p h u h n hai ph n t ñư c s p th t tuy n tính thì ñ u ñ ng c u v i nhau. T ñó suy ra r ng các ki u th t c a các t p h p h u h n ñư c s p th t tuy n tính ñ u là các s th t . Theo quy ư c thì s th t (ki u th t ) c a m t t p h p ñư c s p th t t t có n ph n t ñư c ký hi u là n. Không m t ki u th t nào trong s ω*, η , λ là m t s th t c . Đ nh lý 3.2.1.1 N u ( X , ≤) là m t t p h p ñư c s p th t t t và n u A ⊂ X thì ( A, ≤ A) cũng là m t t p h p ñư c s p th t t t. Nh n xét 3.2.1.1 Cho ( X , ≤) là m t t p h p ñư c s p th t t t và x ∈ X . N u x không ph i ph n t sau cùng trong X thì t p h p { y ∈ X : ( x ≤ y ) ∧ ( x ≠ y)} = { y ∈ X : x p y} là không r ng. Vì t p h p này là m t t p h p con c a X nên theo ñ nh lý 3.2.1.1 ta suy ra nó ñư c s p th t t t và vì v y nó có m t ph n t ñ u tiên. Ph n t này ñư c g i là ph n t ti p sau c a x vì nó theo ngay sau x . T ñó ta có ñ nh lý v ph n t ti p sau kéo theo:
20 Đ nh lý 3.2.1.2 M i ph n t x c a m t t p h p ñư c s p th t t t, tr ph n t sau cùng, n u có, ñ u có m t ph n t ti p sau. N u x0 là ph n t ñ u tiên c a m t t p h p ñư c s p th t t t thì t p h p này không có ph n t x nào mà x p x0 , và vì v y x0 không ph i ph n t ti p sau c ab t kỳ ph n t nào c a t p h p này. M t t p h p ñư c s p th t t t có th có nh ng ph n t khác v i ph n t ñ u tiên và không ph i là nh ng ph n t ti p sau c a b t kỳ ph n t nào. Ví d 3.2.1.3 1 Cho X là m t t p h p g m các s có d ng 1 − (n = 1, 2,...) và s 1. T p h p n X ñó là ñư c s p th t t t, b i quan h “không l n hơn”. S 1 không ph i ph n t ñ u tiên c a X cũng không ph i ph n t ti p sau c a b t kỳ ph n t nào c a X . Cho ( X , ≤) là m t t p h p ñư c s p th t t t. M t t p h p con Y ⊂ X ñư c g i là kho ng ban ñ u c a X n u ñi u ki n sau ñư c th a mãn v i m i x, y ∈ X : (( y ∈ Y ) ∧ ( x ≤ y )) ⇒ ( x ∈ Y ) (3.19) Đi u ki n này nói r ng khi Y ch a m t ph n t y thì nó cũng ch a m i ph n t x ∈ X mà x ≤ y. Đ nh lý 3.2.1.3 Đ i v i m i kho ng ban ñ u Y c a m t t p h p ñư c s p th t t t ( X , ≤) trong ñó X ≠ Y thì có m t ph n t y c a X sao cho: Y = { x ∈ X : ( x ≤ y ) ∧ ( x ≠ y )} = { x ∈ X : x p y} (3.20) Đ nh lý 3.2.1.4 Cho ( X , ≤) là m t t p h p ñư c s p th t t t và R là h các kho ng ban ñ u c a X khác v i X . Khi ñó: quan h bao hàm ⊂ s s p th t tuy n tính h R (3.24) ( X , ≤) là ñ ng c u v i ( R, ⊂) (3.25) Đ nh lý 3.2.1.5 N u ( X , ≤) là m t t p h p ñư c s p th t t t và n u ( X *, ≤ *) là m t t p h p ñư c s p th t tuy n tính ñ ng c u v i ( X , ≤) thì ( X *, ≤ *) cũng là m t t p h p ñư c s p th t t t.