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

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

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}}$ визначаються з початкових елементів послідовності.

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

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

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

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

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

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

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

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

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

• Рекурсія