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

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

Наприклад:

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

a_n+1=a_n+d.

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

a_n+1=a_n·q.

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

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

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

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

Дивіться також

• Рекурсія