Bài viết dưới đây TTnguyen sẽ giới thiệu về hệ thức truy hồi trong toán rời rạc: định nghĩa, phương pháp giải hệ và một số bài tập điển điển hình.
Xem thêm:
- chỉnh hợp lặp và tổ hợp lặp toán rời rạc – Bài tập có lời giải
- bài tập hoán vị chỉnh hợp tổ hợp có lời giải
- bài tập toán rời rạc chương 2 có lời giải
Định nghĩa
Một hệ thức truy hồi thuần nhất tuyến tính bậc k với hệ số hằng là hệ thức truy hồi có dạng:
\(a_{n} = a_{1}a_{n-1} + c_{2}a_{n-2} + … + c_{k}a_{n-k}\)với \(c_{1},c_{2},…,c_{k} \)là hằng số thực khác 0.
Ví dụ:
\(P_{n} = (1.34)P_{n-1}\) là hệ thức truy hồi tuyến tính bậc một.
\(f_{n} = f_{n-1} + f_{n-2}\) là hệ thức truy hồi thuần nhất tuyến tính bậc 2.
Bài tập
Bài 1: Cho dãy số \(a_{n}\) thoả mãn hệ thức truy hồi:
\(a_{n} = 5a_{n-1} – 6a_{n-2}\) và \(a_{0} = 0\) , \(a_{1} =1\)
Hãy giải hệ thức truy hồi trên.
Lời giải
>>Xem thêm:
Bài 2: Giải hệ thức truy hồi: \(a_{n} = 2a_{n-1} + 5a_{n-2} – 6a_{n-3}\) và \(a_{0} = 0\) , \(a_{1} =-4\), \(a_{2} =8\)
Lời giải
Bài 3: Giải hệ thức truy hồi: \(a_{n} = 6a_{n-1} – 9a_{n-2}\) và \(a_{0} = 1\) , \(a_{1} =6\)
Lời giải
Bài 4: Gọi \(a_{n}\) là số dãy bit độ dài n không có 2 bit 0 liền nhau.
a) Tìm hệ thức truy hồi cho \(a_{n}\)
b) Biết giá trị đầu \(a_{1}=2,a_{2}=3\) , giải hệ thức truy hồi trên.
c) Tìm hệ thức truy hồi cho số các xâu nhị phân chứa xâu 00.
Lời giải
a) Tìm hệ thức truy hồi cho \(a_{n}\)
b) Biết giá trị đầu \(a_{1}=2,a_{2}=3\) , giải hệ thức truy hồi trên.
c) Tìm hệ thức truy hồi cho số các xâu nhị phân chứa xâu 00.
Bài 5: Cho biết dân số của Việt Nam năm 2007 là 86 triệu người. Giả sử tốc độ tăng dân số hằng năm là 0,2% mỗi năm. Gọi Dn là dân số của Việt Nam n năm sau 2007.
a) Lập hệ thức truy hồi tính \(D_{n}\)
b) Dân số Việt Nam năm 2020 là bao nhiêu?
Lời giải
Bài 6: Tìm hệ thức truy hồi và điều kiện đầu để tính số chuỗi nhị phân độ dài n có 4 bít 0 liên tiếp. Ứng dụng tính số chuỗi với n=8.
Lời giải
>>>Có thể bạn quan tâm: logic mệnh đề – Bài tập toán rời rạc chương 1 có lời giải
Trên đây là một số bài tập về cách giải hệ thức truy hồi trong toán rời rạc. Cảm ơn các bạn đã theo dõi trên ttnguyen.net
