Generating Functions là một phương pháp để giải quyết các hệ thức truy hồi.
Các bài viết liên quan:
Ta xét dãy a0, a1, a2 …. ar là các số thực. Đối với một số khoảng các số thực có chứa giá trị 0 tại t được cho trước, thì hàm G (t) được xác định bởi chuỗi
Hàm G (t) này được gọi là Generating Functions của dãy ar.
Bây giờ, đối với dãy hằng số 1, 1, 1, 1 ….. hàm tạo là
Nó có thể được diễn đạt như
So sánh, điều này với phương trình (i), chúng tôi nhận được
Đối với, dãy không đổi 1,2,3,4,5, .. Generating Functions là
So sánh, điều này với phương trình (i), chúng tôi nhận được
a0 = 1, a1 = 2, a2 = 3, a3 = 4, v.v.
Generating Functions của Zr, (Z ≠ 0 và Z là hằng số) được cho bởi
Ngoài ra, Nếu a (1) r có Generating Functions G1 (t) và a (2) r có Generating Functions G2 (t), thì λ1 a (1) r + λ2 a (2) r có Generating Functions λ1 G1 (t) + λ2 G2 (t). Ở đây λ1 và λ2 là các hằng số.
Lĩnh vực ứng dụng:
Các hàm tạo có thể được sử dụng cho các mục đích sau:
- Để giải quyết các Recurrence Relations
- Để chứng minh một số đặc điểm tổ hợp
- Để tìm công thức tiệm cận cho các số hạng của chuỗi
Ví dụ: Giải Recurrence Relations
Bằng phương pháp sinh hàm với các điều kiện ban đầu a0 = 2 và a1 = 3.
Giải pháp: Hãy giả sử rằng
Nhân phương trình (i) với tr và tổng từ r = 0 đến ∞, ta có
Bây giờ, đặt a0 = 2 và a1 = 3 vào phương trình (ii) và giải ra, chúng ta nhận được
Đặt t = 1 vào cả hai vế của phương trình (iii) để tìm A. Do đó
Đặt
vào cả hai vế của phương trình (iii) để tìm B. Do đó
Do đó
Do đó,
