Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
G:\Новая папкаРекуррентные соотношения.Стр 1 из 6Следующая ⇒
Часть 4 Некоторые члены последовательности исходя из значений одного или нескольких членов. В задачах комбинаторики это означает уменьшение количества аргументов. Вычислительное соотношения имеют порядок K, если оно позволяет выразить функцию дискретного аргумента. Если задано рекурсивное соотношение k-го порядка, то ему отвечает бесконечно много различных последовательностей. Рекурсивные соотношения (РС) определяют последовательность только в том случае, если заданы k-первых членов этой последовательности. Если при подстановке любого члена последовательности рекуррентное соотношение обращается в множество, то мы будем говорить, что эта последовательность является решением данного рекурсивного соотношения. Пример: Решением этого соотношения будет Решением рекуррентного соотношения будем называть общем, если оно зависит от k произвольных постоянных Путем подбора которых можно получить решение данного соотношения. Общего правила для решения рекуррентных соотношений не имеется. Рассмотрим рекуррентное соотношение k-го порядка вида: (1) , где некоторые числа. Рекуррентное соотношение вида (1) называется линейным рекуррентным соотношением с постоянными коэффициентами. (2) – второй порядок Пусть известны и (2), отсюда вытекает следующее утверждение: Для Таким образом получили второе тождество; следовательно обращает выражение (2) в тождество и является решение рекуррентного соотношения. Запишем следующее квадратное уравнение соответственно по отношению ко (2) (3) Это уравнение назовем характеристическим уравнением для (2) Пусть корень, тогда запишем утверждение (2): Утверждение (2): Последовательность , где n = 1, 2, 3… также является решением соотношения (2), таким образом: , , , тогда подставив эти значения в уравнение (3) получим . Разделим это выражение на и получим: , это тождество очевидно, итак
|