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

Рекурентним співвідношенням називається формула виду 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).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$c_{1}=1$

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

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

Див. також

• Рекурсія