Giải Hệ Thức Truy Hồi - Tài Liệu Học Tập Môn Toán | Toán Rời Rạc | Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội

1
1. VD: Cho dãy số ao = 5, a1 = 8... an=3an-1 - 2an-2
a. Tìm công thức biểu diễn an theo n.
b. Tìm n tối thiểu để an ≥ 100.
Cách giải bài toán này thứ tự như sau. Đây là bình giải, không phải lời giải nhen.
1. Xác định các chỉ số của phương trình đặc trưng:
Chỉ số này tìm thấy ở công thức tính an. Ta thấy an=3an-1 - 2an-2
Bạn nhìn thấy 2 con số tô đỏ chưa. Đó là các hệ số c1 và c2 của phương trình đặc trưng hệ thức truy hồi.
Hệ thức truy hồi của bài toán dạng này là r2 - c1r + c2 = 0
2. Điền các hệ số trên vào hệ thức truy hồi. Rồi viết vào bài làm, câu sau:
Phương trình đặc trưng của hệ thức truy hồi này có dạng r2 - 3r + 2 = 0
Phải giải phương trình hệ thức truy hồi trên để lấy nghiệm. Nghiệm này giải ở giấy nháp thôi,
trừ trường hợp đặc biệt mới phải làm vào giấy thi vì không cần thiết. Sau đó viết vào bài làm
câu thứ 2 hai nghiệm r1 và r2 như sau:
Nghiệm của phương trình hệ thức truy hồi này là 1 và 2.
Sau đó căn cứ vào nghiệm này chỉ ra phương trình truy hồi của phần tử thứ n, không phụ
thuộc vào các phần tử khác, mà chỉ phụ thuộc vào chỉ số n mà thôi. Ở bài toán này ta vừa tìm
ra hai nghiệm, nên viết tiếp câu thứ 3 vào bài làm:
Theo định lý về hệ thức truy hồi, dãy {an} là nghiệm của hệ thức truy hồi khi và chỉ khi:
Hay (thay số vào ta có):
Với α1 và α2 là những hằng số.
Để xác định các hằng số này, ta thay vào các giá trị đầu để nhận được hệ phương trình cần giải:
Thay vào các giá trị đầu ta được hệ phương trình là:
Giải ra ta được α1 =2 và α2 =3.
Vậy biểu thức tính a n n= 2 + 3.2
b. Để tìm n sao cho an ≥ 100 thì giải bất phương trình sau: 2 + 3.2n ≥ 100
→ 2n ≥ (100 - 2)/3 > 32 → 2n > 25 → n > 5
2. Cho dãy số ao = 1, a1 = 2,a = 3... 2 an=3an-2 + 2an-3
a. Tìm công thức biểu diễn an theo n.
b. Tìm n tối thiểu để an ≥ 100.
Bài này khác bài mẫu ở chỗ, công thức của an=3an-2 + 2an-3 không có liên quan đến an-1, nên rất dễ nhầm lẫn.
Vì truy cập xuống tới an-3 nên Phương trình đặc trưng của hệ thức truy hồi này có dạng 1 2 r3 - 3r - 2 = 0
Lưu ý là xuống tới bao nhiêu phần tử thì số mũ của r sẽ lên bấy nhiêu luỹ thừa. Nghiệm của
phương trình hệ thức truy hồi này là -1, -1 và 2.
Theo định lý về hệ thức truy hồi, dãy {an} là nghiệm của hệ thức truy hồi khi và chỉ khi: Hay thay số ta được:
Để xác định các hằng số này, ta thay vào các giá trị đầu để nhận được hệ phương trình cần giải:
Thay vào các giá trị đầu ta được hệ phương trình là:
Thay kết quả vào được:
b. a ≥ 100 khi vế phải ≥ 100. Đây là bất đẳng thứ n
c thuần tuý, ai cũng có thể giải được.
3. Giải đề số 3, câu 2. Năm 2010. Đề luyện.
Giải các hệ thức truy hồi sau biết ao = 2, b0 = 1,... an= 3an-1 + 2bn-1 (1) bn= an-1 + 3bn-1 (2)
Ờ, bài này có khác với tất cả các bài khác ở chỗ nó có 2 chuỗi, quan hệ đan xen với nhau. A
này, b kia và ngược lại. Đan xen thì đan xen chứ,sợ gì.
Từ cái (2) ta suy ra an-1 =b - 3b n
n-1 đúng không, thay cái vào (1) xem sao, ta nhận được: an = 3an-1 + 2bn-1 = 3b - 3b n
n-1 + 2bn-1= 3bn - 7bn-1 (3)
Ô hô, một vế có a một vế toàn b. Từ cái (3) ta suy ra theo tính chất của biểu thức truy hồi an- 1 = 3bn-1 - 7bn-2 (4)
Thay cái (4) vào (2) ta được:
bn= an-1 + 3bn-1 = 3bn-1 - 7bn-2 + 3bn-1 = 6bn-1 - 7bn-2
Thay lòng vòng tí cho vui thôi, bản chất là ta dùng phép thế của hệ phương trình mà. ta có
thể nhìn ngay ra cách thế, sao cho nhanh nhất. Bây giờ ta hãy giải hệ thức truy hồi theo b.
Tương tự ta cũng có thể thế vào để có được hệ thức truy hồi theo a.
4. Hãy tìm nghiệm của hệ thức truy hồi an=2an1 +
5an2  6an3 với các điều kiện ban đầu là a0=7, a = 1 4 và a2=8. Giải:
Đa thức đặc trưng của hệ thức truy hồi được cho là r32r25r+6 và nó có 3 nghiệm
phân biệt là r1=1, r2= 2, r =3. Do đó nghiệm của hệ 3
thức truy hồi đó có dạng: 2 3 a n n n = a.1 + b.( n 2) + c.3 .
Từ các điều kiện ban đầu, ta có:
{a+bc=7,¿{a−2b+3c=−4,¿ ¿
Giải hệ phương trình này, ta nhận được a=5, b=3, c= 1. Vậy nghiệm của hệ thức truy hồi cần tìm là a = 5 + 3( n n 2)n 3 .
5. Gọi a nlà số các xâu nhị phân độ dài n và chứa xâu 000. Hãy tìm hệ thức truy hồi
đối với dãy số (an)nN. Giải: Gọi A là n
tập hợp các xâu nhị phân độ dài n và chứa xâu 000. XA , ta c n ó 4 trường hợp sau:
 X=Y1, trong đó YAn1, số các xâu X trong trường hợp này là an1.
 X=Z10, trong đó ZAn2, số các xâu X trong trường hợp này là an2.
 X=W100, trong đó WAn3, số các xâu X trong trường hợp này là an . 3
 X=T000, trong đó T là xâu nhị phân độ dài n3, số các xâu T trong trường hợp này là 2n3.
Vậy theo nguyên lý cộng, ta có a n3 n=an1+an2+an3+2 . 3 4 4