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

Т.к. первые k членов последовательности можно задавать произвольно, то множество решений рекуррентного соотношения бесконечно.
Каждое решение однозначно определяется заданием первых k членов последовательности (начальными условиями) и называется к-го порядка.
Решение рекуррентного соотношения k - го порядка называется общим, если оно содержит k произвольных постоянных и путем их подбора можно получить любое решение этого соотношения.
Решение, получающееся из общего путем подбора произвольных постоянных, называется частным.

Линейное рекуррентное соотношение имеет вид :
xn+k = a1 xn+k-1 + a2 xn+k-2 + ... + ak xn + B
Если B равно нулю оно называется однородным, при B, не равном нулю, оно называется неоднородным.
Линейное однородное рекуррентное соотношения (ЛОРС) :
xn+k = a1 xn+k-1 + a2 xn+k-2 + ... + ak xn

Решение ЛОРС
где λ - корни характеристического уравнения
Общим решением является
и если λ имеет кратность t,то соответствующее этому корню слагаемое в общем решении можно заменить на:
Для нахождения частного решения необходимо найти постоянные Сі, исходя из начальных условий.

Решение ЛОРС «числа Фиббоначи»
Xn+2 = Xn+1 + Xn - ЛОРС второго порядка
Числа, являющиеся его решениями при н.у. Х0= 0, Х1 = 1, называются числами Фиббоначи.
К числам Фиббоначи приводит следующая задача теории информации. Найти количество способов передачи сообщений (последовательность нулей и единиц), чтобы рядом не оказалось два нуля.
Обозначим Un - количество сообщений которое можно передать с помощью n сигналов (0 или 1) так, чтобы при этом не оказались рядом два сигнала 0. Очевидно, что U0 = 1 (отсутствие сигнала считаем как сообщение),U1 =2.
Все Un+2 сообщений "длины" n+2 можно разбить на 2 класса:
1) те у которых первый сигнал 1 (их число равно Un+1, т.к. второй сигнал может быть любым 0 или 1); 1**
2) те у которых первый сигнал 0 (и следовательно, обязательно второй сигнал 1) их число равно Un. 01*
Следовательно, Un+2=Un+1+Un оказывается числами Фиббоначи со сдвинутыми номерами.

Общее решение рекуррентного соотношения Фиббоначи.
Характеристическое уравнение
Корни уравнения:
общее решение:

Частное решение чисел Фиббоначи
Используем начальные условия: f0 = 0 , f1 = 1
Подставляя их в общее решение, получим:
Находим С1 и С2:
Частное решение соотношения :