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

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

Рекуррентным уравнением называется уравнение, связывающее несколько подряд идущих членов некоторой числовой последовательности. Последовательность, удовлетворяющая такому уравнению, называется рекуррентной последовательностью .

Примеры

• Функция факториала натурального числа удовлетворяет рекуррентной формуле:

  ${\displaystyle n!={\begin{cases}1,&n=0;\\(n-1)!\cdot n,&n\geqslant 1.\end{cases}}}$

• Числа Фибоначчи задаются линейной рекуррентной формулой :

  ${\displaystyle F_{n}={\begin{cases}0,&n=0;\\1,&n=1;\\F_{n-1}+F_{n-2},&n\geqslant 2.\end{cases}}}$

• Значение интеграла ${\displaystyle \textstyle I_{n}=\int \sin ^{n}x\,dx}$ удовлетворяет рекуррентной формуле:

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

• Решение дифференциального уравнения Бесселя ${\displaystyle y''+(1/x)y'+(1-\nu ^{2}/x^{2})y=0}$ может быть записано в виде степенного ряда :

  ${\displaystyle y=\sum \limits _{n=0}^{\infty }a_{n}x^{2n+\nu }.}$

Чтобы определить коэффициенты ${\displaystyle a_{n}}$ , достаточно установить, что ${\displaystyle 4n(n+\nu )a_{n}+a_{n-2}=0}$ для всех ${\displaystyle n\geq 1}$ . После чего сразу получается известный результат:

${\displaystyle a_{n}={\frac {(-1)^{n}a_{0}}{2^{2^{n}}n!(1+\nu )(2+\nu )\cdots (n+\nu )}}.}$

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

  ${\displaystyle a_{2n}={\sqrt {2R^{2}-2R{\sqrt {R^{2}-{\frac {a_{n}^{2}}{4}}}}}},\qquad n\geq 2,}$

где ${\displaystyle R}$ — радиус описанной окружности .

Линейные рекуррентные уравнения

Линейное рекуррентное уравнение с постоянными коэффициентами имеет вид:

${\displaystyle f_{n+r}+a_{1}f_{n+r-1}+a_{2}f_{n+r-2}+\ldots +a_{r}f_{n}=\varphi (n).}$

Здесь ${\displaystyle n}$ — неотрицательные целые числа, ${\displaystyle f_{n}}$ — последовательность чисел, ${\displaystyle a_{1},a_{2},\ldots ,a_{r}}$ — постоянные числа, ${\displaystyle a_{r}\neq 0}$ , ${\displaystyle \varphi (n)}$ — заданная функция от ${\displaystyle n}$ .

Однородные линейные рекуррентные уравнения

Предположим, что последовательность чисел ${\displaystyle f_{0},f_{1},\dots }$ удовлетворяет однородному линейному рекуррентному уравнению ${\displaystyle f_{n+r}+a_{1}f_{n+r-1}+a_{2}f_{n+r-2}+\ldots +a_{r}f_{n}=0}$ , где ${\displaystyle n}$ — неотрицательные целые числа, ${\displaystyle a_{1},\ldots ,a_{r}}$ — заданные постоянные числа и ${\displaystyle a_{r}\neq 0}$ .

Обозначим через ${\displaystyle F(z)}$ производящую функцию последовательности ${\displaystyle f_{0},f_{1},\dots }$ . Построим многочлен ${\displaystyle K(z)=1+a_{1}z+a_{2}z^{2}+\ldots +a_{r}z^{r}}$ . Этот многочлен можно рассматривать как производящую функцию последовательности ${\displaystyle 1,a_{1},a_{2},\ldots ,a_{r},0,0,\dots }$ . Рассмотрим произведение производящих функций ${\displaystyle C(z)=F(z)K(z)}$ . Коэффициент ${\displaystyle c_{n+r}}$ при ${\displaystyle z^{n+r}}$ и ${\displaystyle n\geq 0}$ определяется соотношением ${\displaystyle c_{n+r}=f_{0}0+\ldots +f_{n-1}0+f_{n}a_{r}+\ldots +f_{n+r}1=f_{n+r}+a_{1}f_{n+r-1}+\ldots +a_{r}f_{n}}$ и равен нулю. Это означает, что многочлен ${\displaystyle C(z)}$ имеет степень самое большее ${\displaystyle r-1}$ , следовательно степень числителя рациональной функции ${\displaystyle F(z)={\frac {C(z)}{K(z)}}}$ меньше степени знаменателя.

Характеристическим многочленом линейного рекуррентного уравнения называется многочлен ${\displaystyle g(z)=z^{r}+a_{1}z^{r-1}+\ldots +a_{r}}$ . Корни этого многочлена называются характеристическими. Характеристический многочлен можно представить в виде ${\displaystyle g(z)=(z-\alpha _{1})^{e_{1}}(z-\alpha _{2})^{e_{2}}\cdots (z-\alpha _{s})^{e_{s}}}$ , где ${\displaystyle \alpha _{1},\ldots ,\alpha _{s}}$ — различные характеристические корни, ${\displaystyle e_{1},\ldots ,e_{s}}$ — кратности характеристических корней, ${\displaystyle e_{1}+e_{2}+\ldots +e_{s}=r}$ .

Характеристический многочлен ${\displaystyle g(z)}$ и многочлен ${\displaystyle K(z)}$ связаны между собой соотношением ${\displaystyle K(z)=z^{r}g\left({\frac {1}{z}}\right)}$ . Таким образом,

${\displaystyle K(z)=(1-\alpha _{1}z)^{e_{1}}(1-\alpha _{2}z)^{e_{2}}\cdots (1-\alpha _{s}z)^{e_{s}}.}$

Рациональную функцию можно представить в виде суммы дробей:

${\displaystyle F(z)={\frac {C(z)}{K(z)}}=\sum _{i=1}^{s}\sum _{k=1}^{e_{i}}{\frac {\beta _{ik}}{(1-\alpha _{i}z)^{k}}}.}$

Каждая дробь в этом выражении имеет вид ${\displaystyle \beta (1-\alpha z)^{-k}}$ , поэтому её можно разложить в степенной ряд следующего вида

${\displaystyle \beta (1-\alpha z)^{-k}=\beta \left[1+(-k)(-\alpha z)+\ldots +{\frac {(-k)\cdots (-k-n+1)}{n!}}(-\alpha z)^{n}+\ldots \right]}$ .

Коэффициент при ${\displaystyle z^{n}}$ в этом ряду равен

${\displaystyle {\frac {\beta (n+k-1)\cdots k}{n!}}\alpha ^{n}=\beta {\binom {n+k-1}{n}}\alpha ^{n}=\beta {\binom {n+k-1}{k-1}}\alpha ^{n}.}$

Следовательно, производящая функция ${\displaystyle F(z)=\sum _{n=0}^{\infty }\left(\sum _{i=1}^{s}p_{i}(n)\alpha _{i}^{n}\right)z^{n}}$ и ${\displaystyle f_{n}=\sum _{i=1}^{s}p_{i}(n)\alpha _{i}^{n}}$ является общим решением линейного рекуррентного уравнения, где ${\displaystyle p_{i}(n)}$ — многочлен от ${\displaystyle n}$ степени самое большее ${\displaystyle e_{i}-1}$ .

Пример

Пусть требуется найти решение уравнения ${\displaystyle f_{n+2}-f_{n+1}+f_{n}=0}$ c граничными условиями ${\displaystyle f_{0}=1}$ и ${\displaystyle f_{1}=1}$ .

Данное уравнение имеет характеристический многочлен ${\displaystyle z^{2}-z+1=(z-\alpha _{1})(z-\alpha _{2})}$ , где ${\displaystyle \alpha _{1}={\frac {1}{2}}+i{\frac {\sqrt {3}}{2}}=e^{i{\frac {\pi }{3}}}}$ , ${\displaystyle \alpha _{2}={\frac {1}{2}}-i{\frac {\sqrt {3}}{2}}=e^{-i{\frac {\pi }{3}}}}$ . Общее решение имеет вид ${\displaystyle f_{n}=c_{1}\alpha _{1}^{n}+c_{2}\alpha _{2}^{n}=c_{1}e^{\frac {i\pi n}{3}}+c_{2}e^{\frac {-i\pi n}{3}}}$ . Подставляя ${\displaystyle n=0,1}$ , получаем ${\displaystyle c_{1}+c_{2}=1}$ , ${\displaystyle c_{1}\alpha _{1}+c_{2}\alpha _{2}=1}$ . Получаем значения ${\displaystyle c_{1}={\frac {1}{2}}-i{\frac {1}{2{\sqrt {3}}}}}$ , ${\displaystyle c_{2}={\frac {1}{2}}+i{\frac {1}{2{\sqrt {3}}}}}$ . Таким образом ${\displaystyle f_{n}=\left({\frac {1}{2}}-i{\frac {1}{2{\sqrt {3}}}}\right)\left(\cos \left({\frac {\pi n}{3}}\right)+i\sin \left({\frac {\pi n}{3}}\right)\right)+\left({\frac {1}{2}}+i{\frac {1}{2{\sqrt {3}}}}\right)\left(\cos \left({\frac {\pi n}{3}}\right)-i\sin \left({\frac {\pi n}{3}}\right)\right)=\cos \left({\frac {\pi n}{3}}\right)+{\frac {1}{\sqrt {3}}}\sin \left({\frac {\pi n}{3}}\right)}$ .

Приложения

Существует формула, выражающая общий член линейной рекуррентной последовательности через корни её характеристического многочлена. Например, для последовательности Фибоначчи такой формулой является формула Бине . Рекуррентные формулы используются для описания времени работы алгоритма, рекурсивно обращающегося к самому себе. В такой формуле время, требуемое для решения задачи объемом ввода ${\displaystyle n}$ , выражается через время решения вспомогательных подзадач.

См. также

• Линейная рекуррентная последовательность
• Рекурсивная функция
• Рекурсия
• Основная теорема о рекуррентных соотношениях (упрощенное решение некоторых видов рекуррентных соотношений, возникающих при анализе сложности рекурсивных алгоритмов)

Примечания

Литература

• Фудзисава Т., Касами Т. Математика для радиоинженеров: теория дискретных структур. — М. , издательство=Радио и связь, 1984. — 240 с.