Рекуррентная формула

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

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

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

Примеры

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

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

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

  [math]\displaystyle{ F_n = \begin{cases} 0, & n=0;\\ 1, & n=1; \\ F_{n-1} + F_{n-2}, & n\geqslant 2.\end{cases} }[/math]

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

  [math]\displaystyle{ I_n=\frac{-\cos x\cdot \sin^{n-1} x}{n}+\frac{n-1}{n}I_{n-2}. }[/math]

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

  [math]\displaystyle{ y=\sum\limits_{n=0}^{\infty}a_n x^{2n+\nu}. }[/math]

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

[math]\displaystyle{ a_n =\frac{(-1)^n a_0}{2^{2^n}n! (1+\nu) (2+\nu ) \cdots (n+\nu)}. }[/math]

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

  [math]\displaystyle{ a_{2n}=\sqrt{2R^2- 2R\sqrt{ R^2-\frac{a^2_n}{4}} }, \qquad n\ge 2, }[/math]

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

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

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

[math]\displaystyle{ f_{n+r}+a_{1}f_{n+r-1}+a_{2}f_{n+r-2}+\ldots+a_{r}f_{n}=\varphi(n). }[/math]

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

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

Основная статья: Линейная рекуррентная последовательность

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

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

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

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

[math]\displaystyle{ K(z)=(1-\alpha_{1}z)^{e_{1}}(1-\alpha_{2}z)^{e_{2}}\cdots(1-\alpha_{s}z)^{e_{s}}. }[/math]

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

[math]\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}}. }[/math]

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

[math]\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] }[/math].

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

[math]\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}. }[/math]

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

Пример

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

Данное уравнение имеет характеристический многочлен [math]\displaystyle{ z^{2}-z+1=(z-\alpha_{1})(z-\alpha_{2}) }[/math], где [math]\displaystyle{ \alpha_{1}=\frac{1}{2}+i\frac{\sqrt{3}}{2}=e^{i \frac{\pi}{3}} }[/math], [math]\displaystyle{ \alpha_{2}=\frac{1}{2}-i\frac{\sqrt{3}}{2}=e^{-i \frac{\pi}{3}} }[/math]. Общее решение имеет вид [math]\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}} }[/math]. Подставляя [math]\displaystyle{ n=0, 1 }[/math], получаем [math]\displaystyle{ c_{1}+c_{2}=1 }[/math], [math]\displaystyle{ c_{1}\alpha_{1}+c_{2}\alpha_{2}=1 }[/math]. Получаем значения [math]\displaystyle{ c_{1}=\frac{1}{2}-i\frac{1}{2\sqrt{3}} }[/math], [math]\displaystyle{ c_{2}=\frac{1}{2}+i\frac{1}{2\sqrt{3}} }[/math]. Таким образом [math]\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) }[/math].

Приложения

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

См. также

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

Литература

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