Đang chuẩn bị liên kết để tải về tài liệu:
Bài giảng Toán rời rạc: Công thức truy hồi - Trần Vĩnh Đức

Bài giảng Toán rời rạc: Công thức truy hồi cung cấp cho người học những nội dung kiến thức như: Công thức truy hồi, công thức truy hồi và hàm sinh, số Catalan, công thức truy hồi tuyến tính. Mời các bạn cùng tham khảo để biết thêm nội dung chi tiết. | Công thức truy hồi Trần Vĩnh Đức HUST Ngày 24 tháng 7 năm 2018 CuuDuongThanCong.com https fb.com tailieudientucntt 1 45 Nội dung Ví dụ Công thức truy hồi Công thức truy hồi và hàm sinh Số Catalan Công thức truy hồi tuyến tính CuuDuongThanCong.com https fb.com tailieudientucntt Ví dụ Một quần thể vi trùng có số lượng cá thể tăng gấp đôi sau mỗi giờ. Nếu thoạt đầu có 5 cá thể hỏi sau 5 giờ số lượng của chúng là bao nhiêu an 2an 1 a0 5 CuuDuongThanCong.com https fb.com tailieudientucntt 3 45 Bài tập Hãy tìm công thức tường minh cho dãy an 2an a0 5 CuuDuongThanCong.com https fb.com tailieudientucntt 4 45 Ví dụ Xét một cầu thang với n bậc thang. Có bao nhiêu cách để đi lên cầu thang nếu chúng ta có thể leo lên 1 bậc hoặc 2 bậc trong mỗi bước S1 1 S2 2 Sn 2 Sn 1 Sn với n 1 CuuDuongThanCong.com https fb.com tailieudientucntt 5 45 Ví dụ Có bao nhiêu xâu nhị phân độ dài n không chứa hai bit 0 liên tiếp an 1 an an 1 a1 2 a2 3 CuuDuongThanCong.com https fb.com tailieudientucntt 6 45 Bài tập Hãy dùng kỹ thuật hàm sinh để tìm công thức tường minh cho dãy an 1 an an 1 a1 2 a2 3 CuuDuongThanCong.com https fb.com tailieudientucntt 7 45 Ví dụ Có bao nhiêu xâu tam phân độ dài n không chứa dãy con 012 an 3 3an 2 an a1 3 a2 9 CuuDuongThanCong.com https fb.com tailieudientucntt 8 45 Nội dung Ví dụ Công thức truy hồi Công thức truy hồi và hàm sinh Số Catalan Công thức truy hồi tuyến tính CuuDuongThanCong.com https fb.com tailieudientucntt Công thức truy hồi Định nghĩa Công thức truy hồi đối với dãy số an là công thức biểu diễn an qua một hay nhiều số hạng đi trước của dãy. CuuDuongThanCong.com https fb.com tailieudientucntt 10 45 Ví dụ Xét dãy số an thỏa mãn công thức an an 1 an 2 a0 3a1 5 Từ công thức truy hồi ta có a2 a1 a0 5 3 2 a3 a2 a1 2 5 3 CuuDuongThanCong.com https fb.com tailieudientucntt 11 45 Định nghĩa Một dãy số được gọi là nghiệm của công thức truy hồi nếu các số hạng của nó thỏa mãn công thức truy hồi này. CuuDuongThanCong.com https fb.com tailieudientucntt 12 45 Ví dụ .