Рекуррентная формула

Определение "Рекуррентная формула" в Большой Советской Энциклопедии

Рекуррентная формула (от лат. recurrens, родительный падеж recurrentis — возвращающийся), формула приведения, формула, сводящая вычисление n-го члена какой-либо последовательности (чаще всего числовой) к вычислению нескольких предыдущих её членов. Обычно эти члены находятся в рассматриваемой последовательности «недалеко» от её n-го члена, число их от n не зависит, а n-й член выражается через них достаточно просто. Однако возможны Рекуррентная формула и более сложной структуры. Общая проблематика рекуррентных вычислений является предметом теории рекурсивных функций.
  Примеры. 1) Последовательность j_n — т. н. чисел Фибоначчи — задаётся формулами:
j₀ = 0, j₁ = 1, j_n+2 = j_n+1 + j_n (n > 0)
  Последняя из них является Рекуррентная формула; она позволяет вычислить j₂, j₃ и дальнейшие члены этой последовательности.
2) Пусть

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

Это — Рекуррентная формула, сводящая вычисление I_n к вычислению /₀ или l₁ в зависимости от чётности n.

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