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

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

$x_{n}=a_{1}\cdot x_{n-1}+\dots +a_{d}\cdot x_{n-d}$ для всех $n\geqslant d$

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

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

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

Примеры

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

• последовательности Люка, удовлетворяющие $x_{n}=P\cdot x_{n-1}-Q\cdot x_{n-2}$, в частности:
  • арифметические прогрессии с $(P,Q)=(2,1)$;
  • геометрическая прогрессия с $P\neq Q=0$, где $x_{1}=Px_{0}$;
  • числа Фибоначчи с $(P,Q)=(1,-1)$;
  • числа Люка с $(P,Q)=(1,-1)$;
• числа трибоначчи, удовлетворяющие $x_{n}=x_{n-1}+x_{n-2}+x_{n-3}$.

См. также: Обобщённые числа Фибоначчи

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

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

$\lambda ^{d}-a_{1}\lambda ^{d-1}-\dots -a_{d-1}\lambda -a_{d}.$

А именно, общий член выражается в виде линейной комбинации $d$ последовательностей вида

$x_{n}=\lambda _{k}^{n}\cdot n^{m},$

где $\lambda _{k}$ — корень характеристического многочлена и $m$ — целое неотрицательное число меньшее, чем кратность $\lambda _{k}$.

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

Пример

Для нахождения формулы общего члена последовательности $F_{n}$, удовлетворяющей линейному рекуррентному уравнению второго порядка $F_{n}=b\cdot F_{n-1}+c\cdot F_{n-2}$ с начальными значениями $F_{1}$, $F_{2}$, следует решить характеристическое уравнение

$q^{2}-bq-c=0$.

Если уравнение имеет два различных корня $q_{1}$ и $q_{2}$, отличных от нуля, то для произвольных постоянных $A$ и $B$, последовательность

$F_{n}=A\cdot q_{1}^{n}+B\cdot q_{2}^{n},$

удовлетворяет рекурентному соотношению; остаётся найти числа $A$ и $B$, что

$F_{1}=A\cdot q_{1}+B\cdot q_{2}$ и $F_{2}=A\cdot q_{1}^{2}+B\cdot q_{2}^{2}$.

Если же дискриминант характеристического уравнения равен нулю и значит уравнение имеет единственный корень $q_{1}$, то для произвольных постоянных $A$ и $B$, последовательность

$F_{n}=(A+B\cdot n)\cdot q_{1}^{n}$

удовлетворяет рекурентному соотношению; остаётся найти числа $A$ и $B$, что

$F_{1}=(A+B)\cdot q_{1}$ и $F_{2}=(A+B\cdot 2)\cdot q_{1}^{2}$.

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

$F_{n}=5\cdot F_{n-1}-6\cdot F_{n-2}$; $F_{1}=1$, $F_{2}=-2$.

корнями характеристического уравнения $q^{2}-5\cdot q+6=0$ являются $q_{1}=2$, $q_{2}=3$. Поэтому

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

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

$F_{n}=5\cdot 2^{n-1}-4\cdot 3^{n-1}.$

Приложения

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

История

Основы теории линейных рекуррентных последовательностей были даны в двадцатых годах восемнадцатого века Абрахамом де Муавром и Даниилом Бернулли. Леонард Эйлер изложил её в тринадцатой главе своего «Введения в анализ бесконечно-малых» (1748). Позднее Пафнутий Львович Чебышёв и ещё позже Андрей Андреевич Марков изложили эту теорию в своих курсах исчисления конечных разностей.

См. также

• Разностное уравнение
• Теорема Скулема
• Регистр сдвига с линейной обратной связью
• М-последовательность

Литература

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