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

Лінійною рекурентною послідовністю (лінійною рекурентою) називається будь-яка числова послідовність ${\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 \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). Пізніше Пафнутій Львович Чебишов і ще пізніше ^[ru] виклали цю теорію в своїх курсах числення скінченних різниць.

Див. також

• Різницеве рівняння

Примітки

1. Л. Эйлер, Введение в анализ бесконечно-малых, т. I, M. — Л., 1936, стр. 197—218
2. П. Л. Чебышев, Теория вероятностей, лекции 1879—1880 гг., М. — Л., 1936, стр. 139—147
3. А. А. Марков, Исчисление конечных разностей, 2-е изд., Одесса, 1910, стр. 209—239

Література

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