G:\Новая папкаРекуррентные соотношения.

Часть 4

Некоторые члены последовательности исходя из значений одного или нескольких членов. В задачах комбинаторики это означает уменьшение количества аргументов.

Вычислительное соотношения имеют порядок K, если оно позволяет выразить функцию дискретного аргумента.

Если задано рекурсивное соотношение k-го порядка, то ему отвечает бесконечно много различных последовательностей.

Рекурсивные соотношения (РС) определяют последовательность только в том случае, если заданы k-первых членов этой последовательности.

Если при подстановке любого члена последовательности рекуррентное соотношение обращается в множество, то мы будем говорить, что эта последовательность является решением данного рекурсивного соотношения.

Пример:

Решением этого соотношения будет

Решением рекуррентного соотношения будем называть общем, если оно зависит от k произвольных постоянных

Путем подбора которых можно получить решение данного соотношения.

Общего правила для решения рекуррентных соотношений не имеется.

Рассмотрим рекуррентное соотношение k-го порядка вида:

(1) , где некоторые числа.

Рекуррентное соотношение вида (1) называется линейным рекуррентным соотношением с постоянными коэффициентами.

(2) – второй порядок

Пусть известны и (2), отсюда вытекает следующее утверждение:

Для

Таким образом получили второе тождество; следовательно обращает выражение (2) в тождество и является решение рекуррентного соотношения.

Запишем следующее квадратное уравнение соответственно по отношению ко (2)

(3)

Это уравнение назовем характеристическим уравнением для (2)

Пусть корень, тогда запишем утверждение (2):

Утверждение (2): Последовательность , где n = 1, 2, 3… также является решением соотношения (2), таким образом:

, , , тогда подставив эти значения в уравнение (3) получим . Разделим это выражение на и получим: , это тождество очевидно, итак