Рекуррентные соотношения

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

. (1)

Решение задачи для п дисков выражено через решение задачи с диском. Соотношение (1) является частным случаем рекуррентных соотношений. Однородное рекуррентное соотношение линейное, с постоянными коэффициентами имеет вид

. (2)

Рассмотрим метод решения рекуррентного соотношения (2). Будем искать решение в виде

.

Подставляя это решение в (2), получаем

. (3)

Уравнение (3) называется характеристическим из него можно найти корни . Согласно основной теореме алгебры таких корней равно k. Таким образом, решение соотношения (2) может быть записано в виде

. (4)

Постоянные выбираются из дополнительных условий накладываемых на функцию .

Рассмотрим пример решения рекуррентного соотношения для определения чисел Фибоначчи, это соотношение имеет вид

(5)

Соотношение (5) примем в виде подобном (2)

. (6)

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

. (7)

Корни этого уравнения следующие

. (8)

Общее решение, согласно (4), запишется так

. (9)

Постоянные и определяем из условий

.

Эти условия принимают вид

(10)

Из этой системы легко находим значения константы и

(11)

Частное решение изучаемых рекуррентных соотношений, с учётом (11) и (8) приводится к виду

.

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

. (12)

Решение уравнения (12) является суммой частного решения (12) и общего решения однородного уравнения следующего из (12). Частное решение для случая ищем в виде . Последнюю величину находим из уравнения

.

. (13)

Решение уравнения (12) окончательно принимает вид

. (14)