KỸ THUẬT ĐẾM CAO CẤP
Số lượng các bacteria(vi khuẩn) trong một colonydoublesmỗi giờ. Nếu một
colonybắt đầu với 5 bacteria. Bao nhiêu cái sẽ được bộc lộ ra trong n giờ? Để giải
quyết vấn đề này, hãy gọi an
là số các bacteriakhi kết thúc n giờ. Ví số lượng các
bacteriadoublemỗi giờ, có mối quan hệ
an = 2an－1
với n là số nguyên dương. Mối
quan hệ này, cùng với điều kiện khởi đầu
a0 － 5 , xác định duy nhất an
cho tất cả
các số n nguyên không âm. Chúng ta có thể tìm thấy một công thức cho
tin này.
an từ thông
Một số vấn đề được đếm (countingproblem) mà không thể được giải quyết bằng cách sử dụng các kỹ thuật được thảo luận trong chương 4, nhưng chúng lại có thể được giải quyết bằng cách tindingcác mối quan hệ. được gọi là các quan hệ truy hồi (RecurrenceRelations). Giữa các thuật ngữ của một chuỗi, như là đã được làm trong vấn đề bao gồm bacteria. Chúng ta sẽ tìm hiểu sự đa dạng của các Counting problemmà có thể được mô hình hóa (làm mẫu) sử dụng các quan hệ truy hồi.
Chúng tôi sẽ phát triển các phương thức trong phần này và trong phần dưới để tìm công thức rõ ràng cho các thuật ngữ của các chuỗi mà chắc chắn đáp ứng được các loại quan hệ truy hồi.
