Рекуррентная формула — формула вида a n = f ( n , a n − 1 , a n − 2 , … , a n − p ) {\displaystyle a_{n}=f(n,a_{n-1},a_{n-2},\dots ,a_{n-p})} , выражающая каждый член последовательности a n {\displaystyle a_{n}} через p {\displaystyle p} предыдущих членов и номер члена последовательности n {\displaystyle n} .
Общая проблематика вычислений с использованием рекуррентных формул является предметом теории рекурсивных функций .
Рекуррентным уравнением называется уравнение, связывающее несколько подряд идущих членов некоторой числовой последовательности. Последовательность, удовлетворяющая такому уравнению, называется рекуррентной последовательностью .
Функция факториала натурального числа удовлетворяет рекуррентной формуле: n ! = { 1 , n = 0 ; ( n − 1 ) ! ⋅ n , n ⩾ 1. {\displaystyle n!={\begin{cases}1,&n=0;\\(n-1)!\cdot n,&n\geqslant 1.\end{cases}}} Значение интеграла I n = ∫ sin n x d x {\displaystyle \textstyle I_{n}=\int \sin ^{n}x\,dx} удовлетворяет рекуррентной формуле: I n = − cos x ⋅ sin n − 1 x n + n − 1 n I n − 2 . {\displaystyle I_{n}={\frac {-\cos x\cdot \sin ^{n-1}x}{n}}+{\frac {n-1}{n}}I_{n-2}.} Чтобы определить коэффициенты a n {\displaystyle a_{n}} , достаточно установить, что 4 n ( n + ν ) a n + a n − 2 = 0 {\displaystyle 4n(n+\nu )a_{n}+a_{n-2}=0} для всех n ≥ 1 {\displaystyle n\geq 1} . После чего сразу получается известный результат: a n = ( − 1 ) n a 0 2 2 n n ! ( 1 + ν ) ( 2 + ν ) ⋯ ( n + ν ) . {\displaystyle a_{n}={\frac {(-1)^{n}a_{0}}{2^{2^{n}}n!(1+\nu )(2+\nu )\cdots (n+\nu )}}.} Длина стороны при удвоении числа сторон вписанного правильного n -угольника : a 2 n = 2 R 2 − 2 R R 2 − a n 2 4 , n ≥ 2 , {\displaystyle a_{2n}={\sqrt {2R^{2}-2R{\sqrt {R^{2}-{\frac {a_{n}^{2}}{4}}}}}},\qquad n\geq 2,} где R {\displaystyle R} — радиус описанной окружности . Линейное рекуррентное уравнение с постоянными коэффициентами имеет вид:
f n + r + a 1 f n + r − 1 + a 2 f n + r − 2 + … + a r f n = φ ( n ) . {\displaystyle f_{n+r}+a_{1}f_{n+r-1}+a_{2}f_{n+r-2}+\ldots +a_{r}f_{n}=\varphi (n).} Здесь n {\displaystyle n} — неотрицательные целые числа, f n {\displaystyle f_{n}} — последовательность чисел, a 1 , a 2 , … , a r {\displaystyle a_{1},a_{2},\ldots ,a_{r}} — постоянные числа, a r ≠ 0 {\displaystyle a_{r}\neq 0} , φ ( n ) {\displaystyle \varphi (n)} — заданная функция от n {\displaystyle n} .
Предположим, что последовательность чисел f 0 , f 1 , … {\displaystyle f_{0},f_{1},\dots } удовлетворяет однородному линейному рекуррентному уравнению f n + r + a 1 f n + r − 1 + a 2 f n + r − 2 + … + a r f n = 0 {\displaystyle f_{n+r}+a_{1}f_{n+r-1}+a_{2}f_{n+r-2}+\ldots +a_{r}f_{n}=0} , где n {\displaystyle n} — неотрицательные целые числа, a 1 , … , a r {\displaystyle a_{1},\ldots ,a_{r}} — заданные постоянные числа и a r ≠ 0 {\displaystyle a_{r}\neq 0} .
Обозначим через F ( z ) {\displaystyle F(z)} производящую функцию последовательности f 0 , f 1 , … {\displaystyle f_{0},f_{1},\dots } . Построим многочлен K ( z ) = 1 + a 1 z + a 2 z 2 + … + a r z r {\displaystyle K(z)=1+a_{1}z+a_{2}z^{2}+\ldots +a_{r}z^{r}} . Этот многочлен можно рассматривать как производящую функцию последовательности 1 , a 1 , a 2 , … , a r , 0 , 0 , … {\displaystyle 1,a_{1},a_{2},\ldots ,a_{r},0,0,\dots } . Рассмотрим произведение производящих функций C ( z ) = F ( z ) K ( z ) {\displaystyle C(z)=F(z)K(z)} . Коэффициент c n + r {\displaystyle c_{n+r}} при z n + r {\displaystyle z^{n+r}} и n ≥ 0 {\displaystyle n\geq 0} определяется соотношением c n + r = f 0 0 + … + f n − 1 0 + f n a r + … + f n + r 1 = f n + r + a 1 f n + r − 1 + … + a r f n {\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}} и равен нулю. Это означает, что многочлен C ( z ) {\displaystyle C(z)} имеет степень самое большее r − 1 {\displaystyle r-1} , следовательно степень числителя рациональной функции F ( z ) = C ( z ) K ( z ) {\displaystyle F(z)={\frac {C(z)}{K(z)}}} меньше степени знаменателя.
Характеристическим многочленом линейного рекуррентного уравнения называется многочлен g ( z ) = z r + a 1 z r − 1 + … + a r {\displaystyle g(z)=z^{r}+a_{1}z^{r-1}+\ldots +a_{r}} . Корни этого многочлена называются характеристическими. Характеристический многочлен можно представить в виде g ( z ) = ( z − α 1 ) e 1 ( z − α 2 ) e 2 ⋯ ( z − α s ) e s {\displaystyle g(z)=(z-\alpha _{1})^{e_{1}}(z-\alpha _{2})^{e_{2}}\cdots (z-\alpha _{s})^{e_{s}}} , где α 1 , … , α s {\displaystyle \alpha _{1},\ldots ,\alpha _{s}} — различные характеристические корни, e 1 , … , e s {\displaystyle e_{1},\ldots ,e_{s}} — кратности характеристических корней, e 1 + e 2 + … + e s = r {\displaystyle e_{1}+e_{2}+\ldots +e_{s}=r} .
Характеристический многочлен g ( z ) {\displaystyle g(z)} и многочлен K ( z ) {\displaystyle K(z)} связаны между собой соотношением K ( z ) = z r g ( 1 z ) {\displaystyle K(z)=z^{r}g\left({\frac {1}{z}}\right)} . Таким образом,
K ( z ) = ( 1 − α 1 z ) e 1 ( 1 − α 2 z ) e 2 ⋯ ( 1 − α s z ) e s . {\displaystyle K(z)=(1-\alpha _{1}z)^{e_{1}}(1-\alpha _{2}z)^{e_{2}}\cdots (1-\alpha _{s}z)^{e_{s}}.} Рациональную функцию можно представить в виде суммы дробей:
F ( z ) = C ( z ) K ( z ) = ∑ i = 1 s ∑ k = 1 e i β i k ( 1 − α i z ) k . {\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}}}.} Каждая дробь в этом выражении имеет вид β ( 1 − α z ) − k {\displaystyle \beta (1-\alpha z)^{-k}} , поэтому её можно разложить в степенной ряд следующего вида
β ( 1 − α z ) − k = β [ 1 + ( − k ) ( − α z ) + … + ( − k ) ⋯ ( − k − n + 1 ) n ! ( − α z ) n + … ] {\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]} .Коэффициент при z n {\displaystyle z^{n}} в этом ряду равен
β ( n + k − 1 ) ⋯ k n ! α n = β ( n + k − 1 n ) α n = β ( n + k − 1 k − 1 ) α 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}.} Следовательно, производящая функция F ( z ) = ∑ n = 0 ∞ ( ∑ i = 1 s p i ( n ) α i n ) z n {\displaystyle F(z)=\sum _{n=0}^{\infty }\left(\sum _{i=1}^{s}p_{i}(n)\alpha _{i}^{n}\right)z^{n}} и f n = ∑ i = 1 s p i ( n ) α i n {\displaystyle f_{n}=\sum _{i=1}^{s}p_{i}(n)\alpha _{i}^{n}} является общим решением линейного рекуррентного уравнения, где p i ( n ) {\displaystyle p_{i}(n)} — многочлен от n {\displaystyle n} степени самое большее e i − 1 {\displaystyle e_{i}-1} .
Пример Пусть требуется найти решение уравнения f n + 2 − f n + 1 + f n = 0 {\displaystyle f_{n+2}-f_{n+1}+f_{n}=0} c граничными условиями f 0 = 1 {\displaystyle f_{0}=1} и f 1 = 1 {\displaystyle f_{1}=1} .
Данное уравнение имеет характеристический многочлен z 2 − z + 1 = ( z − α 1 ) ( z − α 2 ) {\displaystyle z^{2}-z+1=(z-\alpha _{1})(z-\alpha _{2})} , где α 1 = 1 2 + i 3 2 = e i π 3 {\displaystyle \alpha _{1}={\frac {1}{2}}+i{\frac {\sqrt {3}}{2}}=e^{i{\frac {\pi }{3}}}} , α 2 = 1 2 − i 3 2 = e − i π 3 {\displaystyle \alpha _{2}={\frac {1}{2}}-i{\frac {\sqrt {3}}{2}}=e^{-i{\frac {\pi }{3}}}} . Общее решение имеет вид f n = c 1 α 1 n + c 2 α 2 n = c 1 e i π n 3 + c 2 e − i π n 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}}} . Подставляя n = 0 , 1 {\displaystyle n=0,1} , получаем c 1 + c 2 = 1 {\displaystyle c_{1}+c_{2}=1} , c 1 α 1 + c 2 α 2 = 1 {\displaystyle c_{1}\alpha _{1}+c_{2}\alpha _{2}=1} . Получаем значения c 1 = 1 2 − i 1 2 3 {\displaystyle c_{1}={\frac {1}{2}}-i{\frac {1}{2{\sqrt {3}}}}} , c 2 = 1 2 + i 1 2 3 {\displaystyle c_{2}={\frac {1}{2}}+i{\frac {1}{2{\sqrt {3}}}}} . Таким образом f n = ( 1 2 − i 1 2 3 ) ( cos ( π n 3 ) + i sin ( π n 3 ) ) + ( 1 2 + i 1 2 3 ) ( cos ( π n 3 ) − i sin ( π n 3 ) ) = cos ( π n 3 ) + 1 3 sin ( π n 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)} .
Существует формула, выражающая общий член линейной рекуррентной последовательности через корни её характеристического многочлена. Например, для последовательности Фибоначчи такой формулой является формула Бине .Рекуррентные формулы используются для описания времени работы алгоритма, рекурсивно обращающегося к самому себе. В такой формуле время, требуемое для решения задачи объемом ввода n {\displaystyle n} , выражается через время решения вспомогательных подзадач.[1]
Фудзисава Т., Касами Т. Математика для радиоинженеров: теория дискретных структур. — М. , издательство=Радио и связь, 1984. — 240 с.