tailieunhanh - Bài giảng Toán rời rạc: Quy nạp - Trần Vĩnh Đức

Bài giảng Toán rời rạc: Quy nạp cung cấp cho người học những nội dung kiến thức như: Nguyên lý quy nạp, quy nạp mạnh, ví dụ chứng minh sai, 15-Puzzle, 8-Puzzle, chuyển hàng, chuyển cột, . Mời các bạn cùng tham khảo. | Quy nạp Trần Vĩnh Đức HUST Ngày 24 tháng 7 năm 2018 https tailieudientucntt 1 37 Tài liệu tham khảo Eric Lehman F Thomson Leighton amp Albert R Meyer Mathematics for Computer Science 2013 Miễn phí Kenneth H. Rosen Toán học rời rạc ứng dụng trong tin học Bản dịch Tiếng Việt https tailieudientucntt 2 37 Nội dung Nguyên lý quy nạp Quy nạp mạnh https tailieudientucntt Nguyên lý quy nạp 880 81 777879 82 3 84 73747576 88 87 8685 72 71 70 69 68 67 666564 63661 260 59 58 5354 557 556 505152 49 48 47 46 45 4443 2 4 4140 9 3 3387 35 34 36 Xét vị từ P n trên N. Nếu 2 3 33133 0 2 2 28 9 2256 7 P 0 đúng và 24 23 22 22109 với mọi n N P n P n 1 1 8 1 1716 cũng đúng 151143 2 110 11 thì P n đúng với mọi n N. 789 56 4 3 2 1 https tailieudientucntt 4 37 Ví dụ Định lý Với mọi n N n n 1 1 2 n 2 Đặt P n là mệnh đề n n n 1 i 2 i 1 https tailieudientucntt 5 37 Chứng minh. Bước cơ sở P 0 đúng. Bước quy nạp Ta sẽ chứng minh với mọi n 0 mệnh đề P n P n 1 đúng. Thật vậy giả sử P n đúng với n là một số nguyên bất kỳ. Vì 1 2 n n 1 1 2 n n 1 n n 1 n 1 2 n 1 n 2 2 nên P n 1 đúng. Theo quy nạp ta có P n đúng với mọi số n N. https tailieudientucntt 6 37 Ví dụ Chứng minh rằng 1 1 1 1 n lt 1 2 4 8 2 với mọi n 1. https tailieudientucntt 7 37 Ví dụ Định lý Với mọi n N ta có n3 n chia hết cho 3. Đặt P n là mệnh đề n3 n chia hết cho 3. https tailieudientucntt 8 37 Chứng minh. Bước cơ sở P 0 đúng vì 03 0 0 chia hết cho 3. Bước quy nạp Ta sẽ chứng minh rằng với mọi n N mệnh đề P n P n 1 đúng. Thật vậy giả sử P n đúng với n là một số nguyên bất kỳ. Vì n 1 3 n 1 n3 3n2 3n 1 n 1 n3 3n2 2n n3 n 3n2 3n n3 n 3 n2 n chia hết cho 3 nên P n 1 đúng. Theo quy nạp ta có P n đúng với mọi số n N. https tailieudientucntt 9 37 Ví dụ chứng minh sai Định lý Sai Mọi con ngựa .