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

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

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

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

Примеры

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

  <math> n! = \begin{cases}

1, & n=0; \\ (n-1)!\cdot n, & n\geqslant 1. \end{cases} </math>

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

  <math>F_n = \begin{cases} 0, & n=0;\\

1, & n=1; \\ F_{n-1} + F_{n-2}, & n\geqslant 2.\end{cases}</math>

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

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

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

  <math>y=\sum\limits_{n=0}^{\infty}a_n x^{2n+\nu}.</math>

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

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

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

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

где R — радиус описанной окружности.

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

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

<math>f_{n+r}+a_{1}f_{n+r-1}+a_{2}f_{n+r-2}+\ldots+a_{r}f_{n}=\varphi(n).</math>

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

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

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

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

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

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

<math>K(z)=(1-\alpha_{1}z)^{e_{1}}(1-\alpha_{2}z)^{e_{2}}\cdots(1-\alpha_{s}z)^{e_{s}}.</math>

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

<math>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>\beta(1-\alpha z)^{-k}</math>, поэтому её можно разложить в степенной ряд следующего вида

<math>\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>z^n</math> в этом ряде равен

<math>\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>F(z)=\sum_{n=0}^{\infty}(\sum_{i=1}^{s}p_{i}(n)\alpha_{i}^{n})z^{n}</math> и <math>f_{n}=\sum_{i=1}^{s}p_{i}(n)\alpha_{i}^{n}</math> является общим решением линейного рекуррентного уравнения, где <math>p_{i}(n)</math> — многочлен от <math>n</math> степени самое большее <math>e_{i}-1</math>.

Пример

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

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

Приложения

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

См. также

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

Литература

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

Отрывок, характеризующий Рекуррентная формула

– Да, ежели бы он, взяв власть, не пользуясь ею для убийства, отдал бы ее законному королю, – сказал виконт, – тогда бы я назвал его великим человеком.
– Он бы не мог этого сделать. Народ отдал ему власть только затем, чтоб он избавил его от Бурбонов, и потому, что народ видел в нем великого человека. Революция была великое дело, – продолжал мсье Пьер, выказывая этим отчаянным и вызывающим вводным предложением свою великую молодость и желание всё полнее высказать.
– Революция и цареубийство великое дело?…После этого… да не хотите ли перейти к тому столу? – повторила Анна Павловна.
– Contrat social, [Общественный договор,] – с кроткой улыбкой сказал виконт.
– Я не говорю про цареубийство. Я говорю про идеи.
– Да, идеи грабежа, убийства и цареубийства, – опять перебил иронический голос.
– Это были крайности, разумеется, но не в них всё значение, а значение в правах человека, в эманципации от предрассудков, в равенстве граждан; и все эти идеи Наполеон удержал во всей их силе.
– Свобода и равенство, – презрительно сказал виконт, как будто решившийся, наконец, серьезно доказать этому юноше всю глупость его речей, – всё громкие слова, которые уже давно компрометировались. Кто же не любит свободы и равенства? Еще Спаситель наш проповедывал свободу и равенство. Разве после революции люди стали счастливее? Напротив. Mы хотели свободы, а Бонапарте уничтожил ее.
Князь Андрей с улыбкой посматривал то на Пьера, то на виконта, то на хозяйку. В первую минуту выходки Пьера Анна Павловна ужаснулась, несмотря на свою привычку к свету; но когда она увидела, что, несмотря на произнесенные Пьером святотатственные речи, виконт не выходил из себя, и когда она убедилась, что замять этих речей уже нельзя, она собралась с силами и, присоединившись к виконту, напала на оратора.
– Mais, mon cher m r Pierre, [Но, мой милый Пьер,] – сказала Анна Павловна, – как же вы объясняете великого человека, который мог казнить герцога, наконец, просто человека, без суда и без вины?
– Я бы спросил, – сказал виконт, – как monsieur объясняет 18 брюмера. Разве это не обман? C'est un escamotage, qui ne ressemble nullement a la maniere d'agir d'un grand homme. [Это шулерство, вовсе не похожее на образ действий великого человека.]
– А пленные в Африке, которых он убил? – сказала маленькая княгиня. – Это ужасно! – И она пожала плечами.
– C'est un roturier, vous aurez beau dire, [Это проходимец, что бы вы ни говорили,] – сказал князь Ипполит.
Мсье Пьер не знал, кому отвечать, оглянул всех и улыбнулся. Улыбка у него была не такая, какая у других людей, сливающаяся с неулыбкой. У него, напротив, когда приходила улыбка, то вдруг, мгновенно исчезало серьезное и даже несколько угрюмое лицо и являлось другое – детское, доброе, даже глуповатое и как бы просящее прощения.
Виконту, который видел его в первый раз, стало ясно, что этот якобинец совсем не так страшен, как его слова. Все замолчали.
– Как вы хотите, чтобы он всем отвечал вдруг? – сказал князь Андрей. – Притом надо в поступках государственного человека различать поступки частного лица, полководца или императора. Мне так кажется.
– Да, да, разумеется, – подхватил Пьер, обрадованный выступавшею ему подмогой.
– Нельзя не сознаться, – продолжал князь Андрей, – Наполеон как человек велик на Аркольском мосту, в госпитале в Яффе, где он чумным подает руку, но… но есть другие поступки, которые трудно оправдать.
Князь Андрей, видимо желавший смягчить неловкость речи Пьера, приподнялся, сбираясь ехать и подавая знак жене.

Вдруг князь Ипполит поднялся и, знаками рук останавливая всех и прося присесть, заговорил:
– Ah! aujourd'hui on m'a raconte une anecdote moscovite, charmante: il faut que je vous en regale. Vous m'excusez, vicomte, il faut que je raconte en russe. Autrement on ne sentira pas le sel de l'histoire. [Сегодня мне рассказали прелестный московский анекдот; надо вас им поподчивать. Извините, виконт, я буду рассказывать по русски, иначе пропадет вся соль анекдота.]
И князь Ипполит начал говорить по русски таким выговором, каким говорят французы, пробывшие с год в России. Все приостановились: так оживленно, настоятельно требовал князь Ипполит внимания к своей истории.
– В Moscou есть одна барыня, une dame. И она очень скупа. Ей нужно было иметь два valets de pied [лакея] за карета. И очень большой ростом. Это было ее вкусу. И она имела une femme de chambre [горничную], еще большой росту. Она сказала…
Тут князь Ипполит задумался, видимо с трудом соображая.
– Она сказала… да, она сказала: «девушка (a la femme de chambre), надень livree [ливрею] и поедем со мной, за карета, faire des visites». [делать визиты.]
Тут князь Ипполит фыркнул и захохотал гораздо прежде своих слушателей, что произвело невыгодное для рассказчика впечатление. Однако многие, и в том числе пожилая дама и Анна Павловна, улыбнулись.
– Она поехала. Незапно сделался сильный ветер. Девушка потеряла шляпа, и длинны волоса расчесались…
Тут он не мог уже более держаться и стал отрывисто смеяться и сквозь этот смех проговорил:
– И весь свет узнал…
Тем анекдот и кончился. Хотя и непонятно было, для чего он его рассказывает и для чего его надо было рассказать непременно по русски, однако Анна Павловна и другие оценили светскую любезность князя Ипполита, так приятно закончившего неприятную и нелюбезную выходку мсье Пьера. Разговор после анекдота рассыпался на мелкие, незначительные толки о будущем и прошедшем бале, спектакле, о том, когда и где кто увидится.


Поблагодарив Анну Павловну за ее charmante soiree, [очаровательный вечер,] гости стали расходиться.
Пьер был неуклюж. Толстый, выше обыкновенного роста, широкий, с огромными красными руками, он, как говорится, не умел войти в салон и еще менее умел из него выйти, то есть перед выходом сказать что нибудь особенно приятное. Кроме того, он был рассеян. Вставая, он вместо своей шляпы захватил трехугольную шляпу с генеральским плюмажем и держал ее, дергая султан, до тех пор, пока генерал не попросил возвратить ее. Но вся его рассеянность и неуменье войти в салон и говорить в нем выкупались выражением добродушия, простоты и скромности. Анна Павловна повернулась к нему и, с христианскою кротостью выражая прощение за его выходку, кивнула ему и сказала: