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

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

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

(8.3)

где

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

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

, то есть изучим соотношение вида

(8.4)

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

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

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

   
   также является решением этого соотношения.

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

   
   

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

   
   и
   
   соответственно и сложим полученные тождества. Получим, что
   

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

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

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

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

   

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

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

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

   
   . Заметим, что наряду с последовательностью
   
   любая последовательность вида
   

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

   

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

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

(8.5)

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

(8.6)

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

, то общее решение соотношения (8.5) имеет вид

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

являются решениями нашего соотношения. А тогда по утверждению 1 и является его решением. Надо только показать, что любое решение соотношения (8.5) можно записать в этом виде. Но любое решение соотношения второго порядка определяется значениями . Поэтому достаточно показать, что система уравнений

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

.
Этими решениями являются



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

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

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

(8.7)

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

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

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

(8.8)

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

вместо ). Мы называли числами Фибоначчи решения соотношения (8.7), удовлетворяющее начальным условиям ( то есть последовательность ). Часто бывает более удобно добавить к этой последовательности вначале числа 0 и 1, то есть рассматривать последовательность Ясно, что эта последовательность удовлетворяет тому же самому рекуррентному соотношению (8.6) и начальным условиям . Полагая в формуле (8.6) , получаем для

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



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

(8.9)

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


Содержание раздела

---