302
правки
Изменения
→Определения
'''Рекуррентная формула''' (англ. ''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>, вместе с заданными первыми p членами, где <tex>p</tex> — порядок рекуррентного соотношения.
}}
Для рекуррентного соотношения, которому удовлетворяет последовательность <tex> \{ a_n \} </tex> мы часто хотим получить выражение для <tex>a_n</tex>. Например, для рекурсивной функции, описывающей сумму чисел натурального рядаФибоначчи: <br><tex>f F_0 = 0,\begin{cases} f(0)qquad F_1 =0; 1,\\ f(qquad F_{n) } = F_{n -1} + f(F_{n-1)2},\quad n \gt 0 geqslant 2, \quad n\end{cases}in Z.</tex>
<tex>a_n</tex> член может быть записан следующим образом: <tex>a_n=\dfrac{1}{\sqrt{5}}\left( \biggl( \dfrac{1+\sqrt{5}}{2} \biggr)^n - \biggl( \dfrac{1-\sqrt{5}}{2} \biggr)^n \right).</tex>
Для этого можно использовать [[Решение_рекуррентных_соотношений#Метод производящих функций | метод производящих функций]] (англ. ''generating function method'').
==Метод производящих функций==
