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

Лінійною рекурентною послідовністю (лінійною рекурентою) називається будь-яка числова послідовність $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 називається порядком послідовності.

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

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

Приклади

Частковими випадками лінійних рекурентних послідовностей є послідовності:

• арифметична прогресія
• геометрична прогресія
• числа Фібоначчі
• числа Люка
• числа трибоначчі
• послідовності Люка

Формула загального члена

Для лінійних рекурентних послідовностей існує формула, яка виражає загальний член послідовності через корені її характеристичного многочлена

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

Див. також

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

Література

• Шаблон:Книга-ру
• Шаблон:Книга-ру
• Шаблон:Стаття
• Шаблон:Книга-ру