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

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

$x_n=a_1\cdot x_{n-1}+\dots +a_d\cdot x_{n-d}$ для всех $n⩾d$

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

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

Частными случаями линейных рекуррентных последовательностей являются последовательности Люка $x_n=P\cdot x_{n-1}-Q\cdot x_{n-2}$, в частности арифметические прогрессии ($(P,Q)=(2,1)$), геометрические прогрессии ($P\ne Q=0$, где $x_1=P{x}_0$), числа Фибоначчи ($(P,Q)=(1,-1)$), числа Люка ($(P,Q)=(1,-1)$); числа трибоначчи, удовлетворяющие $x_n=x_{n-1}+x_{n-2}+x_{n-3}$ и ряд других обобщений чисел Фибоначчи.

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

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

Характеристический многочлен

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

${\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}$.

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга