Линейная рекуррентная последовательность
Линейной рекуррентной последовательностью (линейной рекуррентой) называется всякая числовая последовательность <math>x_0,x_1,\dots</math>, задаваемая линейным рекуррентным соотношением:
- <math>x_n=\sum\limits_{i=1}^d a_ix_{n-i}</math> для всех <math>n\geqslant d</math>
с заданными начальными членами <math>x_0,\dots,x_{d-1}</math>, где d — фиксированное натуральное число, <math>a_1,\dots,a_d</math> — заданные числовые коэффициенты, <math>a_d\ne 0</math>. При этом число d называется порядком последовательности.
Линейные рекуррентные последовательности иногда называют также возвратными последовательностями.
Примеры
Частными случаями линейных рекуррентных последовательностей являются последовательности:
- арифметическая прогрессия
- геометрическая прогрессия
- числа Фибоначчи
- числа Люка
- числа трибоначчи
- последовательности Люка
Формула общего члена
Для линейных рекуррентных последовательностей существует формула, выражающая общий член последовательности через корни её характеристического многочлена
- <math>\lambda^d-a_1 \lambda^{d-1}-\dots-a_{d-1}\lambda - a_d.</math>
Для чисел Фибоначчи такой формулой является формула Бине.
Пример
Для последовательности <math>F_n(F_1,F_2)</math>, удовлетворяющей линейному рекуррентному уравнению второго порядка <math>F_n=bF_{n-1}+cF_{n-2}</math> с начальными значениями <math>F_1</math>, <math>F_2</math>, справедлива формула:
- <math>F_n(F_1,F_2)=F_2F_{n-1}(1,b)+c F_1F_{n-2}(1,b)</math>.
Для того, чтобы найти <math>F_n(1,b)</math> необходимо решить характеристическое уравнение <math>q^2-bq-c=0</math>. Если дискриминант этого уравнения отличен от нуля, то
- <math>F_n(1,b)=\frac{1}{b-2q}((b-q)^n-q^n),</math>
где <math>q</math> — любой из двух корней этого уравнения. Если же дискриминант характеристического уравнения равен нулю, то
- <math>F_n(1,b)=nq^{n-1}.</math>
В частности, для последовательности, определяемой следующим линейным рекуррентным уравнением второго порядка
- <math>F_n=5F_{n-1}-6F_{n-2}</math>; <math>F_1=1</math>, <math>F_2=-2</math>.
корнями характеристического уравнения <math>q^2-5q+6=0</math> являются <math>q_1=2</math>, <math>q_2=3</math>. Поэтому
- <math>F_n(1,b)=\frac{1}{5-2\cdot 2}((5-2)^n-2^n)=3^n-2^n;</math>
- <math>F_n(1,-2)=-2\cdot (3^{n-1}-2^{n-1})-6\cdot (3^{n-2}-2^{n-2}).</math>.
Окончательно:
- <math>F_n(1,-2)=5\cdot 2^{n-1}-4\cdot 3^{n-1}.</math>
Приложения
Линейные рекуррентные последовательности над кольцами вычетов традиционно используются для генерации псевдослучайных чисел.
Напишите отзыв о статье "Линейная рекуррентная последовательность"
Литература
- А. И. Маркушевич. [ilib.mccme.ru/plm/ann/a01.htm Возвратные последовательности]. — Гос. Издательство Технико-Теоретической Литературы, 1950. — Т. 1. — (Популярные лекции по математике).
- М. М. Глухов, В. П. Елизаров, А. А. Нечаев. Глава XXV. Линейные рекуррентные последовательности // Алгебра. — Учебник. В 2-x томах. — М.: Гелиос АРВ, 2003. — Т. 2. — ISBN 8-85438-072-2.
- А. Егоров [kvant.mccme.ru/pdf/2005-05.pdf Числа Пизо] // Квант. — 2005. — № 5. — С. 8—13.
- Чебраков Ю. В. [chebrakov.narod.ru/bbb-2.7.pdf Глава 2.7. Рекуррентные уравнения] // [chebrakov.narod.ru Теория магических матриц. Выпуск ТММ-1]. — СПб, 2010.
Отрывок, характеризующий Линейная рекуррентная последовательность
– Бородино, – поправляя, отвечал другой.Офицер, видимо, довольный случаем поговорить, подвинулся к Пьеру.
– Там наши? – спросил Пьер.
– Да, а вон подальше и французы, – сказал офицер. – Вон они, вон видны.
– Где? где? – спросил Пьер.
– Простым глазом видно. Да вот, вот! – Офицер показал рукой на дымы, видневшиеся влево за рекой, и на лице его показалось то строгое и серьезное выражение, которое Пьер видел на многих лицах, встречавшихся ему.
– Ах, это французы! А там?.. – Пьер показал влево на курган, около которого виднелись войска.
– Это наши.
– Ах, наши! А там?.. – Пьер показал на другой далекий курган с большим деревом, подле деревни, видневшейся в ущелье, у которой тоже дымились костры и чернелось что то.
– Это опять он, – сказал офицер. (Это был Шевардинский редут.) – Вчера было наше, а теперь его.
– Так как же наша позиция?
– Позиция? – сказал офицер с улыбкой удовольствия. – Я это могу рассказать вам ясно, потому что я почти все укрепления наши строил. Вот, видите ли, центр наш в Бородине, вот тут. – Он указал на деревню с белой церковью, бывшей впереди. – Тут переправа через Колочу. Вот тут, видите, где еще в низочке ряды скошенного сена лежат, вот тут и мост. Это наш центр. Правый фланг наш вот где (он указал круто направо, далеко в ущелье), там Москва река, и там мы три редута построили очень сильные. Левый фланг… – и тут офицер остановился. – Видите ли, это трудно вам объяснить… Вчера левый фланг наш был вот там, в Шевардине, вон, видите, где дуб; а теперь мы отнесли назад левое крыло, теперь вон, вон – видите деревню и дым? – это Семеновское, да вот здесь, – он указал на курган Раевского. – Только вряд ли будет тут сраженье. Что он перевел сюда войска, это обман; он, верно, обойдет справа от Москвы. Ну, да где бы ни было, многих завтра не досчитаемся! – сказал офицер.
Старый унтер офицер, подошедший к офицеру во время его рассказа, молча ожидал конца речи своего начальника; но в этом месте он, очевидно, недовольный словами офицера, перебил его.
– За турами ехать надо, – сказал он строго.
Офицер как будто смутился, как будто он понял, что можно думать о том, сколь многих не досчитаются завтра, но не следует говорить об этом.
– Ну да, посылай третью роту опять, – поспешно сказал офицер.
– А вы кто же, не из докторов?
– Нет, я так, – отвечал Пьер. И Пьер пошел под гору опять мимо ополченцев.
– Ах, проклятые! – проговорил следовавший за ним офицер, зажимая нос и пробегая мимо работающих.
– Вон они!.. Несут, идут… Вон они… сейчас войдут… – послышались вдруг голоса, и офицеры, солдаты и ополченцы побежали вперед по дороге.
Из под горы от Бородина поднималось церковное шествие. Впереди всех по пыльной дороге стройно шла пехота с снятыми киверами и ружьями, опущенными книзу. Позади пехоты слышалось церковное пение.
Обгоняя Пьера, без шапок бежали навстречу идущим солдаты и ополченцы.
– Матушку несут! Заступницу!.. Иверскую!..
– Смоленскую матушку, – поправил другой.
Ополченцы – и те, которые были в деревне, и те, которые работали на батарее, – побросав лопаты, побежали навстречу церковному шествию. За батальоном, шедшим по пыльной дороге, шли в ризах священники, один старичок в клобуке с причтом и певчпми. За ними солдаты и офицеры несли большую, с черным ликом в окладе, икону. Это была икона, вывезенная из Смоленска и с того времени возимая за армией. За иконой, кругом ее, впереди ее, со всех сторон шли, бежали и кланялись в землю с обнаженными головами толпы военных.
