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

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

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

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

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

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