Линейная рекуррентная последовательность (линейная рекуррента, возвратная последовательность) — числовая последовательность , задаваемая линейным рекуррентным соотношением: для всех с заданными начальными членами , где — фиксированное натуральное число, — заданные числовые коэффициенты, . При этом число называется порядком последовательности.
Теория линейных рекуррентных последовательностей является точным аналогом теории линейных дифференциальных уравнений с постоянными коэффициентами.
Частными случаями линейных рекуррентных последовательностей являются последовательности Люка , в частности арифметические прогрессии (), геометрические прогрессии (, где ), числа Фибоначчи (), числа Люка (); числа трибоначчи, удовлетворяющие и ряд других обобщений чисел Фибоначчи.
Основы теории линейных рекуррентных последовательностей были даны в 1720-е годы Абрахамом де Муавром и Даниилом Бернулли; Леонард Эйлер изложил её в тринадцатой главе «Введения в анализ бесконечно-малых» (1748)Л. Эйлер, Введение в анализ бесконечно-малых, т. I, M. — Л., 1936, стр. 197—218. Позднее Пафнутий Чебышёв и ещё позже Андрей Марков изложили эту теорию в своих курсах исчисления конечных разностейП. Л. Чебышев, Теория вероятностей, лекции 1879—1880 гг., М. — Л., 1936, стр. 139—147А. А. Марков, Исчисление конечных разностей, 2-е изд., Одесса, 1910, стр. 209—239.
Согласно теореме Скулема нули линейной рекурентной последовательности элементов поля нулевой характеристики (например, рациональных, алгебраических или комплексных чисел) образуют конечное число арифметических прогрессий. Известны алгоритмы определения первого нуля для линейных рекуурентных последовательностей порядка , опрос об алгоритмической разрешимости нахождения первого нуля в общем случае — открытая проблема, известная как .
Среди приложений — применение линейных рекуррентные последовательностей над кольцами вычетов для генерации псевдослучайных чисел.
Характеристический многочлен Для линейных рекуррентных последовательностей существует формула, выражающая общий член последовательности через корни её характеристического многочлена: , общий член выражается в виде линейной комбинации последовательностей вида:
где — корень характеристического многочлена и — целое неотрицательное число меньшее, чем кратность .
Для чисел Фибоначчи такой формулой является формула Бине.
Например, для нахождения формулы общего члена последовательности , удовлетворяющей линейному рекуррентному уравнению второго порядка с начальными значениями , , следует решить характеристическое уравнение . Если уравнение имеет два различных корня и , отличных от нуля, то для произвольных постоянных и , последовательность
удовлетворяет рекурентному соотношению; остаётся найти числа и , что и .
Если же дискриминант характеристического уравнения равен нулю и значит уравнение имеет единственный корень , то для произвольных постоянных и , последовательность:
удовлетворяет рекурентному соотношению; остаётся найти числа и , что и .
В частности, для последовательности, определяемой следующим линейным рекуррентным уравнением второго порядка: ; , корнями характеристического уравнения являются , . Поэтому: . Окончательно: .
Примечания
Литература
Категория:Теория чисел Категория:Ряды и последовательности