Рекуррентная последовательность

Рекурре́нтная после́довательность (от лат. recurrens, род. падеж recurrentis – возвращающийся), последовательность ${\displaystyle a_{0},a_{1},a_{2}}$ ,..., для которой справедливо соотношение вида

${\displaystyle a_{n+p}+c_{1}a_{n+p-1}+...+c_{p}a_{n}=0,}$

где ${\displaystyle c_{1},...,c_{p}}$ – постоянные. Это соотношение позволяет вычислить один за другим члены последовательности, если известны первые ${\displaystyle p}$ членов. Примером рекуррентной последовательности является последовательность чисел Фибоначчи:

${\displaystyle 1,\,1,\,2,\,3,\,5,\,8,\,..}$.

(для неё ${\displaystyle a_{n+2}-a_{n+1}-a_{n}=0}$, ${\displaystyle n\geqslant 0}$, ${\displaystyle a_{0}=a_{1}=1}$). Иногда рекуррентная последовательность называется возвратной последовательностью. Термин «рекуррентность» ввёл А. де Муавр.