Линейная рекуррентная последовательность

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Линейной рекуррентной последовательностью (линейной рекуррентой) называется всякая числовая последовательность , задаваемая линейным рекуррентным соотношением:

для всех

с заданными начальными членами , где d — фиксированное натуральное число,  — заданные числовые коэффициенты, . При этом число d называется порядком последовательности.

Линейные рекуррентные последовательности иногда называют также возвратными последовательностями.

Примеры[править | править вики-текст]

Частными случаями линейных рекуррентных последовательностей являются последовательности:

Формула общего члена[править | править вики-текст]

Для линейных рекуррентных последовательностей существует формула, выражающая общий член последовательности через корни её характеристического многочлена

Для чисел Фибоначчи такой формулой является формула Бине.

Пример[править | править вики-текст]

Для последовательности , удовлетворяющей линейному рекуррентному уравнению второго порядка с начальными значениями , , справедлива формула:

.

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

где  — любой из двух корней этого уравнения. Если же дискриминант характеристического уравнения равен нулю, то

В частности, для последовательности, определяемой следующим линейным рекуррентным уравнением второго порядка

; , .

корнями характеристического уравнения являются , . Поэтому

.

Окончательно:

Приложения[править | править вики-текст]

Линейные рекуррентные последовательности над кольцами вычетов традиционно используются для генерации псевдослучайных чисел.

Литература[править | править вики-текст]