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


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


Этими решениями являются
C_1 = \frac{{b - ar_2 }}{{r_1 - r_2 }},

C_2^{} = \frac{{ar_1 - b}}{{r_1 - r_2 }}.

(Случай, когда оба корня уравнения (8.6) совпадут друг с другом, разберем в следующем пункте.)

Пример на доказанное правило.

При изучении чисел Фибоначчи мы пришли к рекуррентному соотношению

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

(8.7)

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

r^2 = r + 1.

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

r_1 = \frac{{1 + \sqrt 5 }}{2},\quadr_2 = \frac{{1 - \sqrt 5 }}{2}.

Поэтому общее решение соотношения Фибоначчи имеет вид

f(n) = C_1 (\frac{{1 + \sqrt 5 }}{2})^n + C_2 (\frac{{1 - \sqrt 5 }}{2})^n.

(8.8)

(Мы воспользовались сделанным выше замечанием и взяли показатели

n

вместо

n - 1
). Мы называли числами Фибоначчи решения соотношения (8.7), удовлетворяющее начальным условиям
f(0) = 1,f(1) = 2
( то есть последовательность
1, 2, 3, 5, 8, 13, ...
). Часто бывает более удобно добавить к этой последовательности вначале числа 0 и 1, то есть рассматривать последовательность
0, 1, 1, 2, 3, 5, 8 13,...
Ясно, что эта последовательность удовлетворяет тому же самому рекуррентному соотношению (8.6) и начальным условиям
f(0) = 1,f(1) = 2
. Полагая в формуле (8.6)
n = 0,n = 1
, получаем для
C_1^{},C_2

систему уравнений

C_1 + C_2 = 0

\hfill \frac{{\sqrt 5 }} {2}(C_1 - C_2 ) = 1 \hfill

Отсюда находим, что

C_1=-C_2=\frac{1}{\sqrt 5}
и потому
f(n) = \frac{1}{5}[(\frac{{1 + \sqrt 5 }} {2})^n - (\frac{{1 - \sqrt 5 }}{2})^n ].

(8.9)

На первый взгляд кажется удивительным, что это выражение при всех натуральных значениях

n
принимает целые значения.




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



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