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 .

Không thể tạo bản xem trước, hãy bấm tải xuống
TÀI LIỆU MỚI ĐĂNG
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.