Рекурентне співвідношення

Рекурентним співвідношенням називається формула виду a_n+1=F(a_n,a_n-1,...,a_n-k+1), де F деяка функція від k аргументів, яка дозволяє обчислити наступні члени числової послідовності через значення попередніх членів. Рекурентне співвідношення однозначно визначає послідовність a_n, якщо вказано k перших членів послідовності. Рекурентне співвідношення є прикладом рекурсивного визначення послідовності.

Приклади

• Послідовність Фібоначчі:

a_n+1=a_n+a_n-1, a₁=1, a₂=1.

• Рекурентне співвідношення арифметичної прогресії:

a_n+1=a_n+d.

• Рекурентне співвідношення геометричної прогресії:

a_n+1=a_n·q.

• Рекурентне співвідношення послідовності n!:

a_n+1=a_n·(n+1).

• Рекурентне співвідношення (синуса фіксованого кута):

${\displaystyle \sin(n+1)\alpha =2\sin \alpha \cos n\alpha +\sin(n-1)\alpha ,}$.

Лінійне однорідне рекурентне співвідношення з постійними коефіцієнтами

Лінійним однорідним рекурентним співвідношенням з постійними коефіцієнтами порядку ${\displaystyle k}$ є рівняння

${\displaystyle a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{d}a_{n-d},}$

де всі коефіцієнти ${\displaystyle c_{i}}$ постійні.

Ті ж самі коефіцієнти визначають характеристичний многочлен (або "допоміжний многочлен")

${\displaystyle p(t)=t^{d}-c_{1}t^{d-1}-c_{2}t^{d-2}-\cdots -c_{d}}$.

Згідно з основною теоремою алгебри існує ${\displaystyle d}$ коренів рівняння ${\displaystyle p(t)=0}$. Ці корені відіграють вирішальну роль в знаходженні послідовності, яка відповідає заданому рекурентному співвідношенню.

Якщо всі корені ${\displaystyle r_{1},r_{2},\dots ,r_{d}}$ різні, то розв'язок рекурсії має вигляд:

${\displaystyle a_{n}=k_{1}r_{1}^{n}+k_{2}r_{2}^{n}+\cdots +k_{d}r_{d}^{n},}$

де коефіцієнти ${\displaystyle k_{i}}$ визначаються в залежності від значень початкових елементів послідовності ${\displaystyle a_{1},a_{2},\dots ,a_{d}}$.

У випадку коли однакові корені присутні декілька разів (кратні корені) розв'язок рекурсії має інший вигляд. Якщо ${\displaystyle r_{i}\ (i=1,\dots ,s)}$ корінь кратності ${\displaystyle l_{i}}$ (для простого кореня ${\displaystyle l_{i}=1}$), тоді

${\displaystyle a_{n}=\sum _{i=1}^{s}(k_{i1}+k_{i2}n+\cdots +k_{il_{i}}n^{l_{i}-1})r_{i}^{n},}$

де коефіцієнти ${\displaystyle k_{ij}}$ визначаються з початкових елементів послідовності.

Як приклад можна зауважити, що послідовність Фібоначчі задається лінійним однорідним рекурентним співвідношенням з постійними коефіцієнтами порядку два. Застосування наведеного методу дає формулу Біне.

У комбінаториці

Метод розв'язання комбінаторної задачі зведенням до меншої задачі (або задач) називається методом рекурентних співвідношень, а менша задача найчастіше є задачею відносно меншої кількості предметів.

В інформатиці

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

Простий приклад це час, необхідний алгоритму для пошуку елемента в упорядкованому векторі з ${\displaystyle n}$ елементів, в найгіршому випадку.

Примітивний алгоритм полягає в пошуку зліва направо. Найгіршим випадком,буде ситуація в якій потрібний елемент є останнім. В цьому випадку кількість порівнянь буде ${\displaystyle n}$.

Найкращий алгоритм для цієї задачі є бінарний пошук. Він полягає в наступному. Треба спочатку перевірити, чи знаходиться елемент в середині вектора. Якщо ні, то будемо перевіряти, чи середній елемент більше або менше шуканого елемента. Після цього половина вектора може бути відкинута, і алгоритм може працювати знову на половині, що залишилась. Кількість порівнянь описується рекурентним співвідношенням:

${\displaystyle c_{1}=1}$

${\displaystyle c_{n}=1+c_{[n/2]}}$,

що буде близько до функції ${\displaystyle \log _{2}(n)}$.

Див. також

• Рекурсія

Посилання

1. Карнаух Т.О. Комбінаторика [ 22 лютого 2014 у Wayback Machine.]
2. Cormen, T. et al, Introduction to Algorithms, MIT Press, 2009
3. R. Sedgewick, F. Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, 2013