Линейная рекуррентная последовательность

Линейной рекуррентной последовательностью (линейной рекуррентой) называется всякая числовая последовательность $x_0,x_1,\dots$, задаваемая линейным рекуррентным соотношением:

$x_k=\sum\limits_{i=1}^na_ix_{k-i}$ при $k\geqslant n$

с заданными начальными членами $x_0,\dots,x_{n-1}$, где n — фиксированное натуральное число, $a_1,\dots,a_n$ — заданные числовые коэффициенты, $a_n\ne 0$. При этом число n называется порядком последовательности.

Линейные рекуррентные последовательности иногда называют также возвратными последовательностями.

Примеры

Частными случаями линейных рекуррентных последовательностей являются последовательности:

• арифметическая прогрессия
• геометрическая прогрессия
• числа Фибоначчи
• числа Люка
• числа трибоначчи
• последовательности Люка

См. также: en:Generalizations of Fibonacci numbers

Формула общего члена

Для линейных рекуррентных последовательностей существует формула, выражающая общий член последовательности через корни её характеристического многочлена

$\lambda^n-a_1 \lambda^{n-1}-\dots-a_{n-1}\lambda - a_n.$

Для чисел Фибоначчи такой формулой является формула Бине.

Пример

Для последовательности $~F_n(F_1,F_2)$, удовлетворяющей линейному рекуррентному уравнению второго порядка $~F_n=bF_{n-1}+cF_{n-2}$ с начальными значениями $~F_1$, $~F_2$, справедлива формула:

$~F_n(F_1,F_2)=F_2F_{n-1}(1,b)+c F_1F_{n-2}(1,b)$.

Для того, чтобы найти $~F_n(1,b)$ необходимо решить характеристическое уравнение $~q^2-bq-c=0$. Если дискриминант этого уравнения отличен от нуля, то

$F_n(1,b)=\frac{1}{b-2q}((b-q)^n-q^n),$

где $~q$ — любой из двух корней этого уравнения. Если же дискриминант характеристического уравнения равен нулю, то

$~F_n(1,b)=nq^{n-1}.$

В частности, для последовательности, определяемой следующим линейным рекуррентным уравнением второго порядка

$~F_n=5F_{n-1}-6F_{n-2}$; $~F_1=1$, $~F_2=-2$.

корнями характеристического уравнения $~q^2-5q+6=0$ являются $~q_1=2$, $~q_2=3$. Поэтому

$F_n(1,b)=\frac{1}{5-2\cdot 2}((5-2)^n-2^n)=3^n-2^n;$

$F_n(1,-2)=-2\cdot (3^{n-1}-2^{n-1})-6\cdot (3^{n-2}-2^{n-2}).$.

Окончательно:

$F_n(1,-2)=5\cdot 2^{n-1}-4\cdot 3^{n-1}.$

Приложения

Линейные рекуррентные последовательности над кольцами вычетов традиционно используются для генерации псевдослучайных чисел.

Литература

• А. И. Маркушевич Возвратные последовательности. — Гос. Издательство Технико-Теоретической Литературы, 1950. — Т. 1. — (Популярные лекции по математике).
• М. М. Глухов, В. П. Елизаров, А. А. Нечаев Глава XXV. Линейные рекуррентные последовательности // Алгебра. — Учебник. В 2-x томах. — М.: Гелиос АРВ, 2003. — Т. 2. — ISBN 8-85438-072-2
• А. Егоров Числа Пизо // Квант. — 2005. — № 5. — С. 8—13.