Bài giảng Toán rời rạc: Chương 3 - Nguyễn Quỳnh Diệp

Bài giảng Toán rời rạc: Chương 3 Phép quy nạp và đệ quy cung cấp cho người học những kiến thức như: Quy nạp toán học, Đệ quy. Mời các bạn cùng tham khảo để nắm chi tiết nội dung của bài giảng!
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc: Chương 3 - Nguyễn Quỳnh Diệp CHƯƠNG 3 PHÉP QUY NẠP VÀ ĐỆ QUY Nguyễn Quỳnh Diệp diepnq@tlu.edu.vnFile Bài giảng: goo.gl/Y3cpLF hoặc goo.gl/TYxXQD 1 Nguyễn Quỳnh DiệpNỘI DUNG • Quy nạp toán học • Đệ quy Toán rời rạc Nguyễn Quỳnh Diệp 2 3.1. QUY NẠP TOÁN HỌCToán rời rạc Nguyễn Quỳnh Diệp 3QUY NẠP TOÁN HỌCCác phương pháp chứng minh cơ sở: • Chứng minh trực tiếp • Chứng minh gián tiếp • Chứng minh phản chứng • Chứng minh từng trường hợp • Chứng minh tương đương Toán rời rạc Nguyễn Quỳnh Diệp 4QUY NẠP TOÁN HỌC Chứng minh bằng quy nạp • Là kĩ thuật sử dụng để chứng minh các mệnh đề phổ quát trên tập các số nguyên dương, x P(x) với x  Z+. • Bao gồm 2 bước: 1) Bước cơ sở: chỉ ra mệnh đề P(1) là đúng 2) Bước quy nạp: Chứng minh mệnh đề kéo theo P(k)  P(k+1) là đúng với mọi số nguyên dương k Toán rời rạc Nguyễn Quỳnh Diệp 5QUY NẠP TOÁN HỌCVí dụ 1: Chứng minh tổng n số nguyên dương lẻ đầu tiên là n2 1 + 3 + 5 + 7 + … + 2? − 1 = ?2 • Bước cơ sở: P(1) luôn đúng vì 1 = 12 • Bước quy nạp: giả định P(k) đúng với n= k, tức là: 1 + 3 + 5 + 7 + … + 2? − 1 = ? 2 Ta phải chứng minh P đúng với n=k+1. Tức là: P(k+1) = 1 + 3 + 5 + 7 + … + 2? − 1 + 2? + 1 = (? + 1)2 VT = ? 2 + 2? + 1 = (? + 1)2 =VP • Vậy P(n) đúng với mọi n nguyên dương Toán rời rạc Nguyễn Quỳnh Diệp 6QUY NẠP TOÁN HỌCVí dụ 2: Bằng quy nạp toán học, chứng minh bất đẳng thức n< 2n với mọi số nguyên dương n.Ví dụ 3: Bằng quy nạp toán học, chứng minh tổng hữu hạn các số hạng cấp số nhân: ? ?? ?+1 − ? ?? ? = ? + ?? + ?? 2 + ⋯ + ?? ? = ?−1 ?=0 Toán rời rạc Nguyễn Quỳnh Diệp 7 BÀI TẬP  Bài 1: Tìm công thức tính tổng: 1 1 1 + +⋯+ 1.2 2.3 ?. (? + 1) Dùng quy nạp toán học để chứng minh kết quả vừa tìm được. Bài 2: Chứng tỏ rằng với n là số nguyên dương ta có: 12 + 22 + 32 +... + n2 = n(n+1)(2n+1)/6 9 Toán rời rạc Nguyễn Quỳnh Diệp 3.2. ĐỊNH NGHĨA ĐỆ QUYToán rời rạc Nguyễn Quỳnh Diệp 10ĐỆ QUY• Phép đệ quy: Định nghĩa đối tượng qua chính nó Toán rời rạc Nguyễn Quỳnh Diệp 11ĐỆ QUYĐịnh nghĩa đệ quy• Là định nghĩa một dãy, tập hợp bằng cách định nghĩa các số hạng của dãy, tập hợp thông qua các số hạng trước đóCác hàm được định nghĩa bằng đệ quy: 1) Bước cơ sở: cho giá trị của hàm tại 0 2) Bước đệ quy: Cho quy tắc tính giá trị của nó tạimột số nguyên n từ các giá trị nhỏ hơn n Toán rời rạc Nguyễn Quỳnh Diệp 12ĐỆ QUY Ví dụ: Định nghĩa đệ quy của hàm giai thừa F(n) = n! • Bước cơ sở: F(0) = 0! = 1 • Bước đệ quy: - F(1) = 1*F(0) = 1.1 = 1 - F(2) = 2*F(1) = 2.1 = 2 - F(3) = 3*F(2) = 3.2 = 6 - F(n) = n*F(n-1) Toán rời rạc Nguyễn Quỳnh Diệp 13ĐỆ QUY Định nghĩa 1: Các số Fibonaci f0, f1, f2... được định nghĩa bởi các phương trình: f0=0, f1= 1 và fn = fn-1 + fn-2 trong đó n= 2, 3, 4,... Ví dụ: • Tìm các số hạng f2 ,f3 ,f4 ,f5 ,f6 của dãy Fibonacci Toán rời rạc Nguyễn Quỳnh Diệp 14 BÀI TẬP  Bài 3: Hãy định nghĩa đệ quy của hàm sau: a) an, với n  0, n nguyên ? b) ?=? ? Bài 4: Hãy cho định nghĩa đệ quy của dãy {an} , n = 1, 2,... nếu a) an = 6n b) an = 2n + 1 c) an = 10n d) an = 5 15 Toán rời rạc Nguyễn Quỳnh DiệpCÁC TẬP HỢP ĐƯỢC ĐỊNH NGHĨA ĐỆ QUYGiống như định nghĩa bằng đệ quy đối với các hàm, địnhnghĩa đệ quy cho tập hợp cũng gồm 2 phần: bước cơ sở vàbước đệ quy.- Trong bước CƠ SỞ: người ta cho các phần tử xuất phát.- Trong bước ĐỆ QUYy: người ta cho quy tắc để tạo ra các phần tử mới từ các phần tử đã biết Toán rời rạc Nguyễn Quỳnh Diệp 16CÁC TẬP HỢP ĐƯỢC ĐỊNH NGHĨA ĐỆ QUYVí dụ: Cho tập S được định nghĩa như sau: • BƯỚC CƠ SỞ: 3 S • BƯỚC ĐỆ QUY: Nếu x  S và y  S thì x + y  S Hãy chỉ ra các phần tử của tập S sau 3 lần đệ quy Toán rời rạc Nguyễn Quỳnh Diệp 17CÁC THUẬT TOÁN ĐỆ QUY Định nghĩa 1: Một thuật toán được gọi là đệ quy, nếu nó giải một bài toán bằng cách rút gọn liên tiếp bài toán đó tới giai đoạn của chính bài toán ban đầu như ...