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


Линейные рекуррентные соотношения с постоянными коэффициентами


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

f(n + k) = a_1 f(n + k - 1) + a_2 f(n + k - 2) + \ldots + a_k f(n),

(8.3)

где

a_1,a_2,\ldots,a_k
- некоторые числа. Такие соотношения называют линейными рекуррентными соотношениями с постоянными коэффициентами.

Сначала рассмотрим, как решаются такие соотношения при

k = 2
, то есть изучим соотношение вида
f(n + 2) = a_1 f(n + 1) + a_1 f(n).

(8.4)

Решение этих соотношений основано на следующих двух утверждениях.

  1. Если
    f_1 (n)
    и
    f_2 (n)
    являются решениями рекуррентного соотношения (8.4), то при любых числах
    A
    и
    B

    последовательность

    f(n)= Af_1 (n) + Bf_2 (n)
    также является решением этого соотношения.

    В самом деле, по условию, имеем

    f_1 (n + 2) = a_1 f_1 (n + 1) + a_2^{} f_1 (n)

    f_2 (n + 2) = a_1 f_2 (n + 1) + a_2^{} f_2 (n)

    Умножим эти равенства на

    A
    и
    B
    соответственно и сложим полученные тождества. Получим, что
    Af_1 (n + 2) + Bf_2 (n + 2) = a_1 [Af_1 (n + 1) + Bf_2 (n + 1)] + a_2 [Af_1 (n) + Bf_2 (n)].

    А это означает, что

    Af_1 (n) + Bf_2 (n)
    является решением соотношения(8.4).

  2. Если
    r_1
    является корнем квадратного уравнения

    r^2 = a_1 r + a_2,
    то последовательность
    1,r_1,r_1^2,\ldots,r_1^{n - 1},\ldots

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

    f(n + 2) = a_1 f(n + 1) + a_2 f(n).

    В самом деле, если

    f(n) = r_1^{n - 1}
    , то
    f(n + 1) = r_1^n
    и
    f(n + 2) = r_1^{n + 1}
    . Подставляя эти значения в соотношение (8.4), получаем равенство
    1^{n + 1} = a_1 r_1^n + a_2 r_1^{n - 1}.

    Оно справедливо, так как по условию имеем

    r^2 = a_1 r + a_2
    . Заметим, что наряду с последовательностью
    \left\{ {r_1^{n - 1} } \right\}
    любая последовательность вида
    f(n) = r_1^{n + m},n = 1,2,\ldots

    также является решением соотношения (8.4). Для доказательства достаточно использовать утверждение (8.4), положив в нем

    A = r_1^{m + 1},B = 0.

Из утверждений 1 и 2 вытекает следующее правило решения линейных рекуррентных соотношений второго порядка с постоянными коэффициентами.

Пусть дано рекуррентное соотношение

f(n + 2) = a_1 f(n + 1) + a_2 f(n)

(8.5)

Составим квадратное уравнение

r^2 = a_1 r + a_2,

(8.6)

которое называется характеристическим для данного соотношения. Если это уравнение имеет два различных корня

r_1,r_2
, то общее решение соотношения (8.5) имеет вид
f(n) = C_1 r_1^{n - 1} + C_2 r_2^{n - 1}.

Чтобы доказать это правило, заметим сначала, что по утверждению 2

f_1 (n) = r_1^{n - 1},f_2 (n) = r_2^{n - 1}
являются решениями нашего соотношения. А тогда по утверждению 1 и
C_1r_1^n+C_2r_2^n
является его решением. Надо только показать, что любое решение соотношения (8.5) можно записать в этом виде. Но любое решение соотношения второго порядка определяется значениями
f(1),f(2)
. Поэтому достаточно показать, что система уравнений
C_1 + C_2 = a, \hfill

C_1 r_1 + C_2 r_2 = b \hfill

имеет решение при любых

a,b
.


Начало  Назад  Вперед



Книжный магазин