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

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

$x_n=a_1\cdot <!--\; \cdot \; -->x_{n-<!--\; -\; -->1}+\cdots <!--\; \cdots \; -->+a_d\cdot <!--\; \cdot \; -->x_{n-<!--\; -\; -->d}$$x_{n}=a_{1}\cdot x_{n-1}+\dots +a_{d}\cdot x_{n-d}$ для всех $n⩾<!--\; ⩾\; -->d$$n\geqslant d$

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

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

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

ПримерыПравить

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

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

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

Формула общего членаПравить

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

${\mathrm{\lambda <!--\; \lambda \; -->}}^d-<!--\; -\; -->a_1{\mathrm{\lambda <!--\; \lambda \; -->}}^{d-<!--\; -\; -->1}-<!--\; -\; -->\cdots <!--\; \cdots \; -->-<!--\; -\; -->a_{d-<!--\; -\; -->1}\mathrm{\lambda <!--\; \lambda \; -->}-<!--\; -\; -->a_d.$$\lambda ^{d}-a_{1}\lambda ^{d-1}-\dots -a_{d-1}\lambda -a_{d}.$ 

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

$x_n={\mathrm{\lambda <!--\; \lambda \; -->}}_k^n\cdot <!--\; \cdot \; -->n^m,$$x_{n}=\lambda _{k}^{n}\cdot n^{m},$ 

где ${\mathrm{\lambda <!--\; \lambda \; -->}}_k$$\lambda_k$  — корень характеристического многочлена и $m$$m$  — целое неотрицательное число меньшее, чем кратность ${\mathrm{\lambda <!--\; \lambda \; -->}}_k$$\lambda_k$ .

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

ПримерПравить

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

$q^2-<!--\; -\; -->bq-<!--\; -\; -->c=0$$q^{2}-bq-c=0$ .

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

$F_n=A\cdot <!--\; \cdot \; -->q_1^n+B\cdot <!--\; \cdot \; -->q_2^n,$$F_{n}=A\cdot q_{1}^{n}+B\cdot q_{2}^{n},$ 

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

$F_1=A\cdot <!--\; \cdot \; -->q_1+B\cdot <!--\; \cdot \; -->q_2$$F_{1}=A\cdot q_{1}+B\cdot q_{2}$  и $F_2=A\cdot <!--\; \cdot \; -->q_1^2+B\cdot <!--\; \cdot \; -->q_2^2$$F_{2}=A\cdot q_{1}^{2}+B\cdot q_{2}^{2}$ .

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

$F_n=(A+B\cdot <!--\; \cdot \; -->n)\cdot <!--\; \cdot \; -->q_1^n$$F_{n}=(A+B\cdot n)\cdot q_{1}^{n}$ 

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

$F_1=(A+B)\cdot <!--\; \cdot \; -->q_1$$F_{1}=(A+B)\cdot q_{1}$  и $F_2=(A+B\cdot <!--\; \cdot \; -->2)\cdot <!--\; \cdot \; -->q_1^2$$F_{2}=(A+B\cdot 2)\cdot q_{1}^{2}$ .

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

$F_n=5\cdot <!--\; \cdot \; -->F_{n-<!--\; -\; -->1}-<!--\; -\; -->6\cdot <!--\; \cdot \; -->F_{n-<!--\; -\; -->2}$$F_{n}=5\cdot F_{n-1}-6\cdot F_{n-2}$ ; $F_1=1$$F_{1}=1$ , $F_2=-<!--\; -\; -->2$$F_{2}=-2$ .

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

$F_n=-<!--\; -\; -->2\cdot <!--\; \cdot \; -->(3^{n-<!--\; -\; -->1}-<!--\; -\; -->2^{n-<!--\; -\; -->1})-<!--\; -\; -->6\cdot <!--\; \cdot \; -->(3^{n-<!--\; -\; -->2}-<!--\; -\; -->2^{n-<!--\; -\; -->2}).$$F_{n}=-2\cdot (3^{n-1}-2^{n-1})-6\cdot (3^{n-2}-2^{n-2}).$ .

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

$F_n=5\cdot <!--\; \cdot \; -->2^{n-<!--\; -\; -->1}-<!--\; -\; -->4\cdot <!--\; \cdot \; -->3^{n-<!--\; -\; -->1}.$$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.