Hệ thức truy hồi là một trong những nội dung quan trọng trong toán rời rạc, giúp mô tả và giải quyết nhiều bài toán liên quan đến dãy số và các hệ phương trình lặp lại. Trong bài viết này, TTnguyen sẽ cùng bạn tìm hiểu định nghĩa, cách giải, và một số bài tập về hệ thức truy hồi kèm lời giải chi tiết.
Xem thêm:
bài tập toán rời rạc chương 1 có lời giải
1. Hệ thức truy hồi là gì?
Hệ thức truy hồi là một phương pháp mô tả một dãy số trong đó giá trị của một phần tử được xác định dựa trên các phần tử trước đó trong dãy.
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.
2. Các loại hệ thức truy hồi
Hệ thức truy hồi bậc 1:
- Dạng: \(c_1a_{n-1}\)
- Ví dụ: \(P_n=1.5P{n-1}\)
Hệ thức truy hồi bậc 2:
- Dạng: \(a_n=c_1a_{n-1}+c_2a_{n-2}\)
- Ví dụ: \(f_n=f{n-1}+f{n-2}\)
Hệ thức truy hồi cao hơn:
- Dạng: \(a_{n} = a_{1}a_{n-1} + c_{2}a_{n-2} + … + c_{k}a_{n-k}\)
3. Cách giải hệ thức truy hồi
Để giải hệ thức truy hồi, thường áp dụng các phương pháp sau:
Phương trình đặc trưng:
Để giải hệ thức truy hồi thuần nhất tuyến tính, viết phương trình đặc trưng:
\(x^k -c_1x^{k-1}-c_2x^{k-2}-…-c_k=0\)
Giải phương trình để tìm nghiệm của x.
Tìm nghiệm tổng quát:
Nếu phương trình có k nghiệm phân biệt:
\(a_{n} = C_{1}a^{n}_{1} + C_{2}a^{n}_{2} + … + C_{k}a^{n}_{k}\)
Nếu có nghiệm lặp:
\(a_{n} = (C_1 +C_2n+…+C_kn^{r-1})x^{n}_{1}\)
Phương pháp diễn giải trực tiếp:
Dùng các giá trị ban đầu để xây dựng dãy số và nhận diện quy luật.
4. Bài tập hệ thức truy hồi toán rời rạc có lời giải
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
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
Bài viết cùng chủ đề:
