Линейная рекуррентная последовательность | это... Что такое Линейная рекуррентная последовательность? (original) (raw)
Линейной рекуррентной последовательностью (линейной рекуррентой) называется всякая числовая последовательность , задаваемая линейным рекуррентным соотношением:
при
с заданными начальными членами , где n — фиксированное натуральное число, — заданные числовые коэффициенты, . При этом число n называется порядком последовательности.
Линейные рекуррентные последовательности иногда называют также возвратными последовательностями.
Содержание
Примеры
Частными случаями линейных рекуррентных последовательностей являются последовательности:
- арифметическая прогрессия
- геометрическая прогрессия
- числа Фибоначчи
- числа Люка
- числа трибоначчи
- последовательности Люка
Формула общего члена
Для линейных рекуррентных последовательностей существует формула, выражающая общий член последовательности через корни её характеристического многочлена
Для чисел Фибоначчи такой формулой является формула Бине.
Пример
Для последовательности , удовлетворяющей линейному рекуррентному уравнению второго порядка с начальными значениями , , справедлива формула:
.
Для того, чтобы найти необходимо решить характеристическое уравнение . Если дискриминант этого уравнения отличен от нуля, то
где — любой из двух корней этого уравнения. Если же дискриминант характеристического уравнения равен нулю, то
В частности, для последовательности, определяемой следующим линейным рекуррентным уравнением второго порядка
; , .
корнями характеристического уравнения являются , . Поэтому
.
Окончательно:
Приложения
Линейные рекуррентные последовательности над кольцами вычетов традиционно используются для генерации псевдослучайных чисел.
Литература
- А. И. Маркушевич Возвратные последовательности. — Гос. Издательство Технико-Теоретической Литературы, 1950. — Т. 1. — (Популярные лекции по математике).
- М. М. Глухов, В. П. Елизаров, А. А. Нечаев Глава XXV. Линейные рекуррентные последовательности // Алгебра. — Учебник. В 2-x томах. — М.: Гелиос АРВ, 2003. — Т. 2. — ISBN 8-85438-072-2
- А. Егоров Числа Пизо // Квант. — 2005. — № 5. — С. 8—13.