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

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

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

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

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

Примеры

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

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

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

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

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

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

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

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

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

Пример

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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 .
• Чебраков Ю. В. // . — СПб. , 2010.