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

числова послідовність, що задається лінійним рекурентним співвідношенням

Лінійною рекурентною послідовністю (лінійною рекурентою) називається будь-яка числова послідовність , задана лінійним рекурентним співвідношенням:

для всіх

з заданими початковими членами , де d — фіксоване натуральне число,  — задані числові коефіцієнти, . При цьому число d називається порядком послідовності.

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

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

ПрикладиРедагувати

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

Формула загального членаРедагувати

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

 

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

 

де   — корінь характеристичного многочлена і   — ціле невід'ємне число, що не перевищує кратності  .

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

ПрикладРедагувати

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

 .

Якщо рівняння має два різні корені   і  , відмінні від нуля, то для довільних сталих   і  , послідовність

 

задовольняє рекурентне співвідношення; залишається знайти числа   і  , такі, що

  і  .

Якщо ж дискримінант характеристичного рівняння дорівнює нулю і отже, рівняння має єдиний корінь  , то для довільних сталих   і  , послідовність

 

задовольняє рекурентне співвідношення; залишається знайти числа   і  , такі, що

  і  .

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

 ;  ,  .

коренями характеристичного рівняння   є  ,  . Тому

 .

Остаточно:

 

ЗастосуванняРедагувати

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

ІсторіяРедагувати

Основи теорії лінійних рекурентних послідовностей були дані в двадцятих роках вісімнадцятого століття Абрахамом де Муавром і Даніелем Бернуллі. Леонард Ейлер виклав її у тринадцятій главі свого «Вступу до аналізу нескінченно малих» (1748).[1] Пізніше Пафнутій Львович Чебишов і ще пізніше Олександр Олександрович Марков[ru] виклали цю теорію в своїх курсах числення cкінченних різниць.[2][3]

Див. такожРедагувати

ПриміткиРедагувати

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

ЛітератураРедагувати