Большая Советская энциклопедия - рекуррентная формула

(от лат. recurrens, родительный падеж recurrentis — возвращающийся)

формула приведения, формула, сводящая вычисление n-го члена какой-либо последовательности (чаще всего числовой) к вычислению нескольких предыдущих её членов. Обычно эти члены находятся в рассматриваемой последовательности «недалеко» от её n-го члена, число их от n не зависит, а n-й член выражается через них достаточно просто. Однако возможны Р. ф. и более сложной структуры. Общая проблематика рекуррентных вычислений является предметом теории рекурсивных функций (См. Рекурсивные функции).

Примеры. 1) Последовательность φn — т. н. чисел Фибоначчи — задаётся формулами:

φ0 = 0, φ1 = 1, φn+2 = φn+1 + φn (n > 0)

Последняя из них является Р. ф.; она позволяет вычислить φ2, φ3 и дальнейшие члены этой последовательности.

2) Пусть

Нетрудно показать, что для n ≥ 2 выполняется соотношение