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

F(n) = F(n-1) + F(n-2)
В 1202 году вышла книга "Liber Abaci" итальянского ученого Леона́рдо Пиза́нского (прозв. Фибоначчи), где он описал знаменитое рекуррентное соотношение
F(n) = F(n-1) + F(n-2)
Почему же это соотношение такое известное?
Рассмотрим три задачи.

Задача о кроликах
Пусть в огороженном месте имеется пара кроликов (самка и самец) в первый день января. Эта пара кроликов производит новую пару кроликов (самку и самца) в первый день февраля и затем в первый день каждого следующего месяца. Каждая новорожденная пара кроликов становится зрелой уже через месяц и затем через месяц дает жизнь новой паре кроликов.
Сколько пар кроликов будет в огороженном месте через год, то есть через 12 месяцев с начала размножения?

Задача о последовательностях
Требуется подсчитать количество последовательностей длины N , состоящих из 0 и 1, в которых никакие две единицы не стоят рядом.

Задача о мячике на лесенке
На вершине лесенки, содержащей N ступенек, находится мячик, который начинает прыгать по ним вниз, к основанию. Мячик может прыгнуть на следующую ступеньку, на ступеньку через одну.
Требуется определить число всевозможных "маршрутов" мячика с вершины на землю.
Где встречались эти задачи?
Связь задач динамического программирования и рекуррентных соотношений.
Что общего в этих задачах?

Что общего в этих задачах?
Последовательность Фибоначчи возникает при решении всех этих на первый взгляд несвязанных задач.
Можно получить это соотношение отдельно для каждой задачи, а можно установить соответствие между решениями этих задач.
Используя эти задачи можно вывести соотношение для вычисления F(n)

РС порядка k.
Опр.1
Рекуррентное соотношение = РС

Решение РС
Опр.2
Решением рекуррентного соотношения называется последовательность при подстановке которой в соотношение получается тождество.
У одного РС может быть бесконечно много решений.
Для РС порядка К, мы можем первые К-1 элемент задать произвольно.

Простой пример
Назовите какое-нибудь решение РС:
f(n) = 3 * f(n-1)
Назовите:
одно решение;
еще два;
общий вид решения;
А если f(1) = 7.
А нельзя ли обобщить наше решение на большее число РС?

Общее решение РС
Решение РС порядка К называется общим, если оно зависит от К произвольных постоянных С1, С2 … СК и путем подбора этих постоянных можно получить любое решение данного РС.

Линейные РС

планшет
Док-во для К=2

Решение линейных РС с пост. коэф.