Комбинаторные алгоритмы для программистов



             

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


Будем говорить, что рекуррентное соотношение имеет порядок

k
, если оно позволяет выразить
f(n + k)
через
f(n),f(n + 1),\ldots,f(n + k - 1)
. Например,
f(n + 2) = f(n)f(n + 1) - 3f^2 (n + 1) + 1

рекуррентное соотношение второго порядка, а

f(n + 3) = 6f(n)f(n + 2) + f(n + 1)
- рекуррентное соотношение третьего порядка. Если задано рекуррентное соотношение
k
-го порядка, то ему удовлетворяет бесконечно много последовательностей. Дело в том, что первые
k

элементов последовательности можно задать совершенно произвольно - между ними нет никаких соотношений. Но если первые

k
элементов заданы, то все остальные элементы определяются совершенно однозначно - элемент
f(k + 1)
выражается в силу рекуррентного соотношения через
f(1),\ldots,f(k)
элемент
f(k + 2)
- через
f(2),\ldots,f(k + 1)
и т.д.

Пользуясь рекуррентным соотношением и начальными членами, можно один за другим выписывать члены последовательности, причем рано или поздно получим любой ее член. Однако при этом придется выписать и все предыдущие члены - ведь не узнав их, мы не узнаем и последующих членов. Но во многих случаях нужно узнать только один определенный член последовательности, а остальные не нужны. В этих случаях удобнее иметь явную формулу для

n
-го члена последовательности. Некоторая последовательность является решением данного рекуррентного соотношения, если при подстановке этой последовательности соотношение тождественно выполняется. Например, последовательность
2,4,8,\ldots,2^n,\ldots

является одним из решений рекуррентного соотношения

f(n + 2) = 3f(n + 1) - 2f(n).

В самом деле, общий член этой последовательности имеет вид

f(n) = 2^n
. Значит,
f(n + 2) = 2^{n + 2},f(n + 1) = 2^{2n + 1}
. Но при любом
n
имеет место тождество
2^{n + 2} = 3 \cdot 2^{n + 1} - 2 \cdot 2^n
. Поэтому
2^n
является решением указанного соотношения.

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

k
-го порядка называется общим, если оно зависит от
k
произвольных постоянных
C_1,C_2,\ldots,C_k

и путем подбора этих постоянных можно получить любое решение данного соотношения. Например, для соотношения

f(n + 2) = 5f(n + 1) - 6f(n)

(8.1)

общим решением будет

f(n) = C_1 2^n + C_2 3^n.

(8.2)

В самом деле, легко проверить, что последовательность (8.2) обращает (8.1) в тождество. Поэтому нам надо только показать, что любое решение нашего соотношения можно представить в виде (8.2). Но любое решение соотношения (8.1) однозначно определяется значениями

f(1)
и
f(2)
. Поэтому нам надо доказать, что для любых чисел
a
и
b




Содержание    Вперед