Рекуррентные соотношения. Возвратные последовательности

Рекуррентным соотношением называется соотношение вида , которое позволяет вычислить все члены последовательности , если заданы ее первые k членов.

Пример 2.11. Формула задает арифметическую прогрессию.

Последовательность называется возвратной, если для всех n и некоторого k выполняется где p_i = const.

Пример 2.12. Геометрическая прогрессия – это возвратная последовательность, так как . Следовательно, выполняется

Многочлен называется характеристическим для возвратной последовательности.

Множество всех последовательностей, удовлетворяющих данному рекуррентному соотношению, называется общим решением.

Описание общего решения имеет аналоги с описанием решения обыкновенного дифференциального уравнения с постоянными коэффициентами. Пусть l – корень характеристического уравнения. Тогда общее решение рекуррентного соотношения можно найти следующим образом:

1. если l_i – корень кратности 1 (i=1,…,k), то общее решение имеет вид где c_i = const (i=1,…,k).

2. если l_i – корень кратности r_i (i=1,…,k), то общее решение имеет вид , где – произвольные константы (i=1,…,n, j=1,…,r_i).

Зная общее решение рекуррентного соотношения, по начальным условиям можно найти неопределенные постоянные и тем самым получить частное решение рекуррентного уравнения с данными начальными условиями.

Пример 2.13. Найти последовательность {a_n}, удовлетворяющую рекуррентному соотношению

Составим характеристический многочлен

Для нахождения корней сгруппируем слагаемые .

Составим характеристическое уравнение Его корнями являются числа . Следовательно, общее решение рекуррентного соотношения имеет вид: . Используя начальные условия, получим систему:

решая которую находим с₁=1, с₂= 1, с₃=1. Таким образом, .