3.3. Неоднородные линейные рекуррентные соотношения

Неоднородное линейное рекуррентное соотношение имеет вид

где величина в общем случае является функцией от Общее решение соотношения (3.3.1) представляет собой сумму частного решения неоднородного уравнения (3.3.1) (т.е. любого решения, которое ему удовлетворяет) и общего решения соответствующего ему однородного соотношения (3.2.1), которое находится рассмотренным способом. Общих способов определения частного решения нет, однако для специальных значений существуют стандартные приемы определения Рассмотрим на примере в некотором роде универсальную процедуру, которая позволяет сразу находить общее решение неоднородного уравнения (3.3.1).

Задача. Найти если известно, что

Умножив левую и правую части рекуррентного соотношения на получим

Суммирование последнего уравнения для всех дает

Свойства операций с производящими функциями позволяют данное выражение привести к виду

Учитывая, что запишем

Сравнивая коэффициенты при заключаем, что

(см. скан)

Задача. Найти число замкнутых маршрутов длины по ребрам треугольника Длину ребра принять равной единице. Начальная и конечная точка маршрутов — вершина А.

Решение. Введем обозначения: число замкнутых маршрутов длины из вершины А в вершину число маршрутов длины из вершины А в вершину число маршрутов длины из вершины А в вершину С.

Очевидно, что из условия симметрии задачи Величины же связаны системой рекуррентных соотношений:

С учетом последнего равенства система приводится к виду

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

Решение данного соотношения получим согласно изложенной выше теории.

Характеристический полином

Отсюда

Перепишем в развернутом виде по степеням

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