Tham khảo tài liệu 'một số vấn đề về thuật toán part 2', 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ả | . Phương pháp quy nạp toán học 25 Ví dụ . Chứng minh rằng vớimọin e N n 0 0 đẳng thức sau đứng l 2 --- n y - Chứng minh. Bước cơ SỞ . Với n 1 ta có 1 1 1 1 2 mệnh đề đúng. Bước quy nạp . Ta kí hiệu S n 1 2-1 F n giả sử mệnh đề đúng với n nghĩà là S n Ta phải chứng minh mệnh đề cũng đứng với n 1 tức lầ s n 1 rc -y- 2 . Thật vậy. S n 1 S n n 1 I 1 ì - -y - n. 1 theo giả thiết quy nạp __2 n . n -y ị l _ n2 3n 2 _ n 1 n 2 - 2 2 Trong toán rời rạc người ta kí hiệu 2S là tập các tập con của tập hợp s. Kí hiệu js là sô phần tử của tập hợp 5. Ta chứng minh khẳng định sau Ví dụ . Nêu s ĩà một tập hợp và 5 n thỉ 25 2 . Chứng minh. Ta có thế kiểm tra một tập có hai phần tử a í n 2 thì chúng có 4 22 tập hợp con 0 đ Ế và đ . Trong trường hợp n 3 a b c có cạc tập hợp con là những tập hợp con ồ trường hợp n 2 cộng thêm với các tập hợp đó thêm vào phần tử c. Ta có ý tưởng chứng minh theo quy nạp Bước cơ sỏ Nếu n 0 thì s 0 vâ 2S 0 . Vậy 25 1 2 . Bước quy nạp Nêu n 0 ta chọn c 5. Đặt tập hợp T 5 c . Theo giả thiết quy nạp ta có 2T I 2 1. Những tập hợp con của 5 không chứa c có số lượng là sô lượng của tập hợp 2r do dó có số lượng 2 1. Sô lượng những tập hợp con chứa c là tất cả tập hợp trên thêm c vào nên nó cũng có sô lượng ỉà 2 . Tổng lại có ị2s 2n i 2 -1 1 2 . Đó là điều cần chứng minh. 26 Chương 1. Công cụ để phân tích và thiết kế thuật toán Khi đánh giá các hàm tính toán người ta cũng thường dùng phương pháp quy nạp toán học. Ví dụ đánh giá tổng một lũy thừa như sau Ví dụ . Chứng minh rằng với mọi sốnguỵên r l tổn tại hằng số n c 0 sao cho if cnr i vớỉmọin. jt i Chứng minh. Ta chứng minh quy nạp theo rt Bước cơ sở Nếu n 1 thì vế trái của bất đăng thức cần chứng minh là lr 1. Vế phải của bất đãng thức là c. lr 1 c do đó ta chọn c lớn hơn 1 bâ t kì thì bất đãng thức đều đúng. Bước quỵ nạp . Với n 1 giả sủ đã có kết luân đúng tr c n-l r l. 1 1 Cộng hai vế bất đẳng thức trên với nr itr c l-l l nr. l Để đạt được mục đích cần chứng minh ta chỉ cần chứng minh bât đảng
