tailieunhanh - Toán rời rạc và một số vấn đề liên quan (P12)

Tham khảo tài liệu 'toán rời rạc và một số vấn đề liên quan (p12)', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Vậy có tất cả 351 5 346 số c 1. 1999 là nghiệm của phương trình f n 0. Ví dụ 5. Cho a 2 và hàm số a n N R xác định như sau í 0 7ĩ a 0 1 a l a a n 1 - 2 a n az n 1 n e N . Với k 6 N dặt Chứng minh rằng W 4o 5O 5w Supf k 1 2 a - Va2 4 . ke 2 X Lời giải . Ta có 1 1 1 2 a 2 3b l a b a2 - 2 b2 Ạr a2 - 4 6 - ị I . b bz b J Ta phải chứng minh f k 2 a- x a2 - 4 Q 1 VfceN và ỏ vế phải của 1 không thể thay Q bởi số nhỏ hơn. Từ định nghĩa của hàm số và từ cách đặt số b ta có @ 0 -2 2 -2 0 í y 6 -0 a3 @w -2 a - 2 - O4 ả O2 y è 0 Bằng phương pháp quy nạp ta chứng minh được w 65 0 O2 À 0 0 I 2n-1 2n-2 - 2 l J 2n-1 a n ỏ2 l ỏ4 1 ò2n 1 M với M ồ2 l ồ4 4-1 ỏ2n 1 . Mặt khác g 2 i ò 2 i ỉ 1 ỉ- Do b l b- 0 . Từ các kết quả trên ta có íl o 1 b b3 2n_1 1 ồ2 1 ỏ2 l ỏ4 1 62 1 4 1 b2n 4-1 1 b 154 b2 b4 b2n 1 b2 52 1 54 1 62 1 64 1 2n 1 L 2 Ta sẽ chứng minh với mọi ai 0 ỉ 6 ta luôn có S V ũj. 1_ỉ-__ Í3Ì 1 ữl l ữ2 1 1 ữi l ữ2 1 n Thật vậy có Sỵ 1 ------ 3 đúng với n 1. 1 ữi 1 ai v J y Giả sứ 3 đúng đến n khi đó dặt p 1 4- ai l a2 1 an ta cố ọ _ ọ 1 __ 1 1 Qn l - 1 I p. l a 1 p p. l a 1 p. l o l Vậy 3 cũng đúng với n 1 tức là theo nguyên lý quy nạp 3 đúng với mọi n N . Theo 3 ta có VT 2 1 - ò2 4 . ỏ2n i 1 VTW L Vậy 2 đúng nên 1 đúng. Mặt khác khi cho 5 1 2 2 ta có VT 2 - 1 nên ở VP 2 không thể thay 1 bởi số nhỏ hơn hay là ở VP 1 không thể thay Q bởi sế nhỏ hơn. Tóm lại ta được Supf k Q - 2 a ỵ a2 4 đpcm . ke 2 Ví dụ 6. Cho Sn 1 2 72 . Phần tử j E Sn được gọi lầ điểm bất động của song ánh p Sn Sn nếu p j j. Gọi f n là sổ song ánh không có điểm bất động còn g n là số song ánh có đúng một diêm bất động Sn Sn. Tìm giá trị lớn nhất và giả trị nhỏ nhất của H rì với n f n ỡ n h n Ễ N . Lời giải . Gọi p là một song ánh Sn Sn mà có đúng một điểm bất động j. Có n cách chọn j G Sn và f n 1 cách lập các song ánh Sn j Sn mà không có điểm bất động. Vậy ở n n n-l 1 Vn 2 Bây giờ gọi r là song ánh Sn Sn mà không có điểm bất động. Khi đó r l j với j 1 và có n 1 cách chọn j như vậy.