ТОР 5 статей: Методические подходы к анализу финансового состояния предприятия Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века Характеристика шлифовальных кругов и ее маркировка Служебные части речи. Предлог. Союз. Частицы КАТЕГОРИИ:
|
Рекуррентные соотношения
Последовательность 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).
Не нашли, что искали? Воспользуйтесь поиском:
|