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

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

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

Члены геометрической прогрессии u 0, u 1, u 2,… со знаменателем q связаны рекуррентным соотношением

un +1 = qun.

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

u 0, u 1, u 2,… связаны рекуррентным соотношением

un +2 = 2 un +1 – un.

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

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

un +1 = (n + 1) un

(при u 0 = 1).

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

k k −1 k

Cn 1  Cn

 Cn,

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

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

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

n +1

Рис. 1

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

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

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

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

D 1 = D 0 + 1;

D 2 = D 1 + 2;

………………

Dn = Dn –1 + n.

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

Dn = D 0 + 1 + 2 +…+ n.

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

Dn = 1 +

n (n  1).

Не нашли, что искали? Воспользуйтесь поиском: