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

Последовательность u0, u1, u2,… называют рекуррентной, если указана зависимость общего члена последовательности от предыдущих и заданы значения необходимого числа начальных членов. Саму зависимость иногда называют рекуррентностью.

Примерами рекуррентных последовательностей могут служить арифметические и геометрические прогрессии.

Члены геометрической прогрессии u0, u1, u2,… со знаменателем q связаны рекуррентным соотношением

un+1 = qun.

Члены произвольной арифметической прогрессии

u0, u1, u2,… связаны рекуррентным соотношением

un+2 = 2un+1 – un.

Последовательность факториалов 1, 1, 2, 6, …, n!,…

определяется рекуррентным соотношением

un+1 = (n + 1)un

(при u0 = 1).

Как рекуррентость может трактоваться формула

k k −1 k

Cn 1  Cn

 Cn ,

связывающая биномиальные коэффициенты.

В качестве еще одного примера рассмотрим задачу о разбиении плоскости прямыми.

Пусть Dn – число областей, на которые разбивают плоскость n прямых общего положения (таких, что никакие три из них не пересекаются в общей точке и никакие две прямые не параллельны). Ясно, что D0 = 1, D2 = 2. Предположим, что на плоскости уже проведено n прямых, и посмотрим, сколько новых областей добавляется при проведении «новой» n + 1-й прямой (рис. 1).

n +1

Рис. 1

Каждую область, по которой проходит эта прямая, она рассекает на две, поскольку все области выпуклы. Таким образом, общее число областей увеличится на число областей, через которые проходит n + 1-я прямая. Двигаясь по n + 1-й прямой в одном направлении, мы пересечем границы областей n раз по числу «старых» прямых. Значит, n + 1-я прямая пройдет через n + 1 область (в последовательности область – граница – … – область – граница – область число областей на единицу больше, чем число границ).

В результате получаем рекуррентное соотношение

Dn+1 = Dn + (n + 1).

Чтобы найти замкнутое выражение для членов последовательности Dn, просуммируем следующие равенства:

D1 = D0 + 1;

D2 = D1 + 2;

………………

Dn = Dn–1 + n .

После сокращений получаем

Dn = D0 + 1 + 2 +…+n .

Следовательно,

Dn = 1 +

n(n  1) .