3.2. Линейные рекуррентные соотношения

Рассмотрим последовательность Будем говорить, что задано однородное линейное рекуррентное соотношение с постоянными коэффициентами порядка если для членов последовательности выполняется равенство

где постоянные величины. Выражение (3.2.1) позволяет вычислить очередной член последовательности по предыдущим гчленам. Ясно, что, задав начальные значения можно последовательно определить все члены последовательности. Мы рассмотрим общий метод решения (т.е. поиска как функции от рекуррентного соотношения (3.2.1).

Для решения задачи достаточно найти производящую функцию

последовательности Введем обозначение для полинома

и рассмотрим произведение

Непосредственным умножением можно убедиться, что это полином, степень которого не превышает так как коэффициенты при согласно уравнению (3.2.1), равны

Характеристическим полиномом соотношения (3.2.1) называется

Выполним разложение на линейные множители

где

Сравнивая запишем Отсюда

Данное разложение на множители используем для представления

в виде суммы простых дробей:

Таким образом, является суммой функций вида

Тогда выражение (3.2.4) примет вид

Данное разложение является производящей функцией последовательности Для определения необходимо найти коэффициент при в разложении (3.2.5).

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

Решение.

Выполним данное умножение: . Таким образом, .

Характеристический полином Отсюда Значения величин находим методом неопределенных коэффициентов: Наконец, принимая во внимание (3.1.2),

С другой стороны, Поэтому, сравнивая коэффициенты при одинаковых степенях заключаем, что