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 https 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 https 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 https 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 https 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 https 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 https 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 https 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 https 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 https 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. https 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 https 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. https tailieudientucntt 12 45 Ví dụ .
