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

Рекуррентная формула — формула вида $a_n=f(n,\, a_{n-1},\, a_{n-2},\, \ldots,\, a_{n-p} )$, $n\ge p+1$, выражающая каждый член последовательности a_n ($n\in \mathbb N$) через $\,p$ предыдущих членов.

Общая проблематика рекуррентных вычислений является предметом теории рекурсивных функций.

Примеры использования рекуррентных формул

• Вычисление факториала натурального числа:

$\,n!=(n-1)!\cdot n$, причём $\,1!=1$.

• Вычисление чисел Фибоначчи задаётся формулами: $\,a_0 = 0$,

$\,a_1 = 1$, $\,a_{n+2} = a_{n+1} + a_{n}$ ($\,n > 0$).

• Вычисление интеграла вида $I_n=\int\sin ^n x\,dx$:

$I_n=\frac{-\cos x\cdot \sin^{n-1} x}{n}+\frac{n-1}{n}I_{n-2}$.

• Решение дифференциального уравнения Бесселя

$\,y'' +(1/x)y' +(1-\nu^2/x^2)y=0$ может быть записано в виде степенного ряда: $y=\sum\limits_{n=0}^{\infty}a_n x^{2n+\nu}$. Чтобы определить коэффициенты $\,a_n$, достаточно установить, что $\,4n(n+\nu)a_n +a_{n-2}=0$, $n\ge 1$. После чего сразу получается известный результат: $a_n =\frac{(-1)^n a_0}{2^{2^n}n! (1+\nu) (2+\nu ) \cdots (n+\nu)}$.

• Длина стороны при удвоении числа сторон правильного вписанного многоугольника:

$a_n=\sqrt{2R^2- 2R\sqrt{ R^2-\frac{a^2_{n-1}}{4}} }$, $n\ge 2$. Здесь $\,R$ — радиус описанной окружности

• Существует формула, позволяющая решить рекуррентное уравнение второго порядка $~F_n=bF_{n-1}+cF_{n-2}$ с начальными значениями $~F_1=r_1$, $~F_2=r_2$.

Через $~F_n(\alpha,\beta)$ будем обозначать n-ый член последовательности, для которой $~F_1=\alpha$, $~F_2=\beta$. Тогда справедлива формула $~F_n(r_1,r_2)=F_n(1,b)-(b-r_2)F_{n-1}(1,b)+c(r_1-1)F_{n-2}(1,b)$.

Для того, чтобы найти $~F_n(1,b)$ необходимо решить характеристическое уравнение $~q^2-bq-c=0$. Если дискриминант этого уравнения отличен от нуля, то

$F_n(1,b)=\frac{1}{b-2q}((b-q)^n-q^n),$

где $~q$ — любой из двух корней этого уравнения. Если же дискриминант характеристического уравнения равен нулю, то

$~F_n(1,b)=nq^{n-1}.$

Пример. $~F_n=5F_{n-1}-6F_{n-2}$; $~F_1=1$, $~F_2=-2$. Находим корни характеристического уравнения $~q^2-5q+6=0$: $~q_1=2$, $~q_2=3$.

$F_n(1,b)=\frac{1}{5-2\cdot 2}((5-2)^n-2^n)=3^n-2^n;$

$F_n(1,-2)=1\cdot (3^n-2^n)-7\cdot (3^{n-1}-2^{n-1}).$.

Окончательно:

$F_n=5\cdot 2^{n-1}-4\cdot 3^{n-1}.$

См. также

• Рекурсивная функция
• Рекурсия