'''Рекуррентная формула''' (англ. ''recurrence relation'') — формула вида <tex>a_n=f(n, a_{n-1}, a_{n-2}, \dots, a_{n-p} ) </tex>, выражающая каждый следующий член последовательности <tex>a_n</tex> через <tex>p</tex> предыдущих членов и номер члена последовательности <tex>n</tex>.
}}
Пусть последовательность <tex>(a_0, a_1, a_2, … )</tex> удовлетворяет некоторому рекуррентному соотношению. Часто мы хотим получить выражение для <tex>a_n</tex> (при <tex>n\geqslant 0</tex>) в замкнутой форе (в виде конечного количества математических объектов), то есть решить рекуррентное соотношение. Например, для рекурсивной функции, описывающей сумму чисел натурального ряда:
<tex>
f = \begin{cases} f(0)=0; \\ f(n) = n + f(n-1),\quad n \gt 0 \end{cases}</tex>
Часто мы хотим явно выразить <tex>na_n</tex>-ый член последовательности, то есть решить рекуррентное соотношение. Например, для рекурсивной функции, описывающей сумму чисел натурального рядаможет быть записан следующим образом: <tex> f a_n= \begindfrac{1}{\sqrt{cases5}} f\left( \biggl(0)=0; \dfrac{1+\sqrt{5}}{2} \ f(nbiggr) = n + f(^n-1),\quad n biggl( \gt 0 dfrac{1-\endsqrt{5}}{cases2}</tex> <tex>\biggr)^n\right).</tex>-ый член может быть записан следующим образом:
Для этого можно использовать [[Решение_рекуррентных_соотношений#Метод производящих функций | метод производящих функций]] (англ. ''generating Function Method'').
может быть переведена в замкнутую форму: <tex>f = \dfrac{n(n+1)}{2}</tex>. Для этого можно использовать [[Решение_рекуррентных_соотношений#Метод производящих функций | метод производящих функций]] (англ. ''generating Function Method'').
==Общая схема==
Пусть последовательность <tex>(a_0, a_1, a_2, … )</tex> удовлетворяет некоторому рекуррентному соотношению. Мы хотим получить выражение для <tex>a_n</tex> (при <tex>n\geqslant 0</tex>) в замкнутом виде (если это возможно). [[Производящая_функция| Производящие функции]] позволяют делать эту работу почти решать рекуррентные соотношение механически по одному и тому же алгоритму. Рассмотрим общую схему на простом примере, который позволит продемонстрировать базовые приёмы работы.
Задано линейное однородное рекуррентное соотношение порядка <tex>2</tex> с постоянными коэффициентами:
