Đang chuẩn bị liên kết để tải về tài liệu:
GIÁO TRINH TOÁN RỜI RẠC - CHƯƠNG II BÀI TOÁN ĐẾM_4

Phương pháp cơ bản để giải hệ thức truy hồi tuyến tính thuần nhất là tìm nghiệm dưới dạng an = rn, trong đó r là hằng số. Chú ý rằng an = rn là nghiệm của hệ thức truy hồi | CHƯƠNG II BÀI TOÁN ĐẾM Phương pháp cơ bản để giải hệ thức truy hồi tuyến tính thuần nhất là tìm nghiệm dưới dạng an rn trong đó r là hằng số. Chú ý rằng an rn là nghiệm của hệ thức truy hồi an c1an-1 c2an-2 . ckan.k nếu và chỉ nếu rn c1rn-1 c2rn-2 . ckrn-k hay rk - c1rk-1 - c2rk-2 - . - ck-1r - ck 0. Phương trình này được gọi là phương trình đặc trưng của hệ thức truy hồi nghiệm của nó gọi là nghiệm đặc trưng của hệ thức truy hồi. Mệnh đề Cho c1 c2 . ck là các số thực. Giả sử rằng phương trình đặc trưng rk c1rk 1 c2rk 2 . ck-1r ck 0 có k nghiệm phân biệt r1 r2 . rk. Khi đó dãy an là nghiệm của hệ thức truy hồi an c1an-1 c2an-2 . ckan-k nếu và chỉ nếu an a1r1n a2r2n . akrkn với n 1 2 . trong đó a1 a2 . ak là các hằng số. Thí dụ 14 1 Tìm công thức hiển của các số Fibonacci. Dãy các số Fibonacci thỏa mãn hệ thức fn fn-1 fn-2 và các điều kiện đầu f0 0 và f1 1. Các nghiệm đặc trưng là r1 1 y5 và r2 22 1y5. Do đó các số Fibonacci được cho bởi công thức fn a1 2 n a2 1 - n Các điều kiện ban đầu f0 0 a1 a2 và fi 1 a1 1 zi-75 . -. . 1 1 a2 . Từ hai phương trình này cho ta a1 -C a2 --C. Do đó v 2 x V5 V5 các số Fibonacci được cho bởi công thức hiển sau fn T5 1 V5 n 1 1 5 n - x5 2 2 Hãy tìm nghiệm của hệ thức truy hồi an 6an-1 - 11an.2 6an-3 với điều kiện ban đầu a0 2 H 5 và a2 15. Đa thức đặc trưng của hệ thức truy hồi này là r3 - 6r2 11r - 6. Các nghiệm đặc trưng là r 1 r 2 r 3. Do vậy nghiệm của hệ thức truy hồi có dạng an a11n a22n a33n. Các điều kiện ban đầu a0 2 a1 a2 a3 H 5 a1 a22 a33 a2 15 a1 a24 a39. Giải hệ các phương trình này ta nhận được a1 1 a2 1 a3 2. Vì thế nghiệm duy nhất của hệ thức truy hồi này và các điều kiện ban đầu đã cho là dãy an với an 1 2n 2.3n. 23 2.6. QUAN HỆ CHIA ĐỂ TRỊ. 2.6.1. Mở đầu Nhiều thuật toán đệ quy chia bài toán với các thông tin vào đã cho thành một hay nhiều bài toán nhỏ hơn. Sự phân chia này được áp dụng liên tiếp cho tới khi có thể tìm được lời giải của bài toán nhỏ một cách dễ dàng. Chẳng hạn ta tiến hành việc tìm kiếm nhị phân bằng