Як вирішувати рекурентні співвідношення?
- Записати рекурентне співвідношення та початкові дані для нього в наступному вигляді (якщо порядок співвідношення дорівнює k) a0 = …, …
- Помножити кожен рядок на z у відповідній мірі zk⋅ak і скласти всі вирази для n≥0. …
- Вирішити отримане рівняння щодо G(z).
Рекурентним рівнянням називається рівняння, що зв'язує кілька поспіль членів, що йдуть, деякою числовою послідовністю. Послідовність, яка задовольняє таке рівняння, називається рекурентної послідовністю.
Рекурентні обчислення — це такі обчислення, В яких кожен елемент послідовності виражається через попередні члени та їх номери.