12-10-2023
Линейной рекуррентной последовательностью (линейной рекуррентой) называется всякая числовая последовательность , задаваемая линейным рекуррентным соотношением:
с заданными начальными членами , где n — фиксированное натуральное число, — заданные числовые коэффициенты, . При этом число n называется порядком последовательности.
Линейные рекуррентные последовательности иногда называют также возвратными последовательностями.
Содержание |
Частными случаями линейных рекуррентных последовательностей являются последовательности:
Для линейных рекуррентных последовательностей существует формула, выражающая общий член последовательности через корни её характеристического многочлена
Для чисел Фибоначчи такой формулой является формула Бине.
Для последовательности , удовлетворяющей линейному рекуррентному уравнению второго порядка с начальными значениями , , справедлива формула:
Для того, чтобы найти необходимо решить характеристическое уравнение . Если дискриминант этого уравнения отличен от нуля, то
где — любой из двух корней этого уравнения. Если же дискриминант характеристического уравнения равен нулю, то
В частности, для последовательности, определяемой следующим линейным рекуррентным уравнением второго порядка
корнями характеристического уравнения являются , . Поэтому
Окончательно:
Линейные рекуррентные последовательности над кольцами вычетов традиционно используются для генерации псевдослучайных чисел.
Линейная рекуррентная последовательность.