Вычисление линейных рекуррентных последовательностей

Последовательность называется линейной рекуррентной, если существуют такие коэффициенты , что для любого n справедливо равенство . Для задания линейной рекуррентной последовательности, кроме ее коэффициентов, необходимо знать первые k членов , которые называются начальными условиями. Рассмотрим задачу выражения n-го члена последовательности через его номер и начальные условия.

Обозначим через вектор столбец, состоящий из k компонент , через — матрицу размерами вида . По правилу перемножения матриц имеем: . Многократным применением полученной формулы выводим . Задача вычисления n-го члена последовательности свелась, тем самым, к вычислению матрицы .

Характеристический многочлен матрицы А равен . Разделим многочлен на с остатком. Пусть , где - остаток от деления. Подставив вместо λ матрицу А, получим . По теореме Гамильтона-Кэли каждая матрица является корнем своего характеристического уравнения, то есть , где 0 - нулевая матрица. Таким образом, , и задача вычисления свелась к вычислению многочлена r(λ).

Разложим многочлен на линейные множители , где . Для каждого неотрицательного j строго меньшего справедливо равенство , где - j-ая производная характеристического многочлена. Продифференцировав j раз равенство и, подставив в него , получим . Этими условиями многочлен r(λ) степени k-1 определяется однозначно. В литературе задача вычисления многочлена по таким условиям носит название «интерполяционный многочлен Лагранжа-Сильвестра».

В качестве примера вычислим n-ый член линейной рекуррентной последовательности , где . Положим . Характеристический многочлен равен . Остаток от деления на удовлетворяет соотношениям и . Единственный многочлен первой степени, удовлетворяющий этим условиям, равен . Таким образом, и .