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

Рекуррентным соотношением называется соотношение вида , которое позволяет вычислить все члены последовательности , если заданы ее первые 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. Таким образом, .