РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ
РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ
(от лат. recur-rens, род. падеж recurrentis - возвращающийся) - однотипные ф-лы, к-рые связывают между собой идущие друг за другом нек-рой последовательности (это может быть последовательность чисел, ф-ций и т. д.). В зависимости от природы объектов, связанных Р. с., эти соотношения могут быть алгебраическими, функциональными, дифференциальными, интегральными и т. п.
Наиб. известный класс Р. с.- это рекуррентные ф-лы для специальных функций.
Так, для цилиндрических функций Z m (x
)P. с. имеют вид
Они позволяют по ф-ции Z m0 (x
)найти ф-ции Z m (x
)п-ри т
= т
0 b
1, т
0 b 2
и т. д. либо, напр., по значениям ф-ций 
в нек-рой точке х
0 . 0 найти (в численных расчётах) значение любой из ф-ций
В этой же точке (здесь m
0 - любое вещественное число).
Др. важный класс Р. с. дают многочисленные методы последовательных приближений (см. Итераций метод);
сюда же примыкают и методы возмущений теории.
В квантовой механике есть ещё один вид Р. с., связывающих между собой векторы в гильбертовом пространстве состояний.
Напр., стационарные гармония, осциллятора параметризуются целыми неотрицательными числами. Соответствующие векторы, обозначаемые , где n
- целое, при разных n
могут быть получены друг из друга действием операторов рождения а +
и уничтожения а
:
Эти соотношения можно разрешить, выразив любой вектор через (наинизшее энергетич. состояние, h =
0):
Обобщением этой конструкции является представление вторичного квантования
в квантовой статистич. механике и квантовой теории поля (см. Фока
пространство).
Типичный пример Р. с. в статистич. механике - ур-ния для частичных ф-ций распределения, образующие цепочку Боголюбова (см. Боголюбова уравнения);
знание таких ф-ций позволяет найти все термодинамич. характеристики системы.
В квантовой теории поля динамич. содержится, напр., в Грина функциях.
Для их вычисления используют разл. приближения, чаще всего - расчеты по теории возмущений. Альтернативный подход основан на интегродифференциальных Дайсона уравнениях,
являющихся Р. с.: ур-ние для двухточечной ф-ции Грина содержит четырёхточечную и т. д. Как и ур-ния Боголюбова, эту систему удаётся решать, лишь "оборвав" цепочку (место "обрыва" выбирается обычно из физ. соображений и определяет получаемое ).
Ещё один вид Р. с. в квантовой теории поля - У орда тождества
в теориях калибровочных полей.
Эти тождества также представляют собой цепочку интегродифференциальных соотношений, связывающих между собой ф-ции Грина с разл. числом внешних линий, p являются следствием калибровочной инвариантности теории. Решающую роль они играют для проверки калибровочной симметрии при проведении процедуры перенормировки.
Наконец, сама - тоже рекуррентная процедура: на каждом шаге (в каждой следующей петле) используются контрчлены, полученные из вычисления диаграмм с меньшим числом петель (подробнее см. R-операция). А. М. Малокостов.
Физическая энциклопедия. В 5-ти томах. - М.: Советская энциклопедия . Главный редактор А. М. Прохоров . 1988 .
Смотреть что такое "РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ" в других словарях:
рекуррентные соотношения - — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN recurrence relations … Справочник технического переводчика
- (функции Вебера) общее название для специальных функций, являющихся решениями дифференциальных уравнений, получающихся при применении метода разделения переменных для уравнений математической физики, таких как уравнение Лапласа, уравнение… … Википедия
Или считалка Джозефуса известная математическая задача с историческим подтекстом. Задача основана на легенде, что отряд Иосифа Флавия, защищавший город Йодфат, не пожелал сдаваться в плен блокировавшим пещеру превосходящими силам римлян.… … Википедия
Пафнутий Львович Чебышёв В математике последовательностью ортогональных многочленов называют бесконечную последовательность действительных многочленов … Википедия
Эта статья предлагается к удалению. Пояснение причин и соответствующее обсуждение вы можете найти на странице Википедия:К удалению/22 ноября 2012. Пока процесс обсуждени … Википедия
Последовательность Падована это целочисленная последовательность P(n) с начальными значениями и линейным рекуррентным соотношением Первые значения P(n) таковы 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, 265 … Википедия
Многочлены Эрмита определённого вида последовательность многочленов одной вещественной переменной. Многочлены Эрмита возникают в теории вероятностей, в комбинаторике, физике. Эти многочлены названы в честь Шарля Эрмита. Содержание 1… … Википедия
- (функции Бесселя) решения Zv(z)ур ния Бесселя где параметр (индекс) v произвольное действительное или комплексное число. В приложениях чаще встречается ур ние, зависящее от четырёх параметров: решения к рого выражаются через Ц … Физическая энциклопедия
Метод решения системы линейных алгебраич. уравнений А х= b с эрмитовой невырожденной матрицей А. Среди прямых методов он наиболее эффективен при реализации на ЭВМ. Вычислительная схема метода в общем случае основана на факторизации эрмитовой… … Математическая энциклопедия
Модифицированные функции Бесселя это функции Бесселя от чисто мнимого аргумента. Если в дифференциальном уравненни Бесселя заменить на, оно примет вид Это уравнение называется модифицированным уравнением Бессел … Википедия
Общим решением рекуррентного соотношения (1) называется множество всех последовательностей, удовлетворяющих этому соотношению.
Частным решением соотношения (1) называется одна из последовательностей, удовлетворяющих этому соотношению.
Пример 1¢. Последовательность a n =a 0 +nd a n =a n - 1 +d . Это - формула общего члена арифметической прогрессии с разностью d и с начальным членом прогрессии a 0 .
Пример 2¢. Последовательность b n =b 0 ×q n является общим решением соотношения b n =b n - 1 ×q . Это - формула общего члена геометрической прогрессии со знаменателем q ¹0 и с начальным членом прогрессии b 0 .
Пример 3¢. Так называемая формула Бине j n =является частным решением соотношения j n =j n - 2 +j n - 1 при j 0 =j 1 =1.
Так как простые корни x 1 ,…,x k попарно различные, то D¹0. Значит, система (5) имеет (единственное) решение.
Задача 1. Найти общий член геометрической прогрессии по формуле (4).
Решение b n =qb n - 1 имеет вид . Поэтому .
Задача 2. Найти общее решение соотношения Фибоначчи a n + 2 =a n +a n + 1 .
Решение . Характеристический многочлен рекуррентного соотношения a n + 2 =a n +a n + 1 имеет вид . Поэтому .
Приведем без доказательства следующее обобщение теоремы 1.
Теорема 2 . Пусть характеристический многочлен однородного линейного рекуррентного соотношения (3) имеет k корней: a 1 кратности , …, a k кратности , , . Тогда общее решение рекуррентного соотношения (3) имеет следующий вид:
Задача 3. Найти общее решение соотношения .
Решение. Характеристический многочлен имеет корень 2 кратности 3. Поэтому .
Замечание . Общее решение неоднородного линейного соотношения (2) можно найти как сумму общего решения однородного линейного соотношения (3) и частного решения неоднородного линейного соотношения (2).
4. Производящие функции. Формальный ряд a 0 +a 1 x +a 2 x 2 +…+a k x k +… называется производящей функцией последовательности a 0 ,a 1 ,a 2 ,…,a k ,…
Производящая функция является или сходящимся рядом, или расходящимся рядом. Два расходящихся ряда могут быть равны как функции, но быть производящимися функциями различных последовательностей. Например, ряды 1+2x +2 2 x 2 +…+2 k x k +… и 1+3x +3 2 x 2 +…+3 k x k +… определяют одну и ту же функцию (равную 1 в точке x =1, неопределенную в точках x >1), но являются производящими функциями различных последовательностей.
Свойства производящих функций последовательностей:
сумма (разность) производящих функций последовательностей a n и b n равна производящей функции сумме (разности) последовательностей a n +b n ;
произведение производящих функций последовательностей a n и b n является производящей функцией свёртки последовательностей a n и b n :
c n =a 0 b n +a 1 b n - 1 +…+a n - 1 b 1 +a n b 0 .
Пример 1. Функция является производящей для последовательности
Пример 2. Функция является производящей для последовательности 1, 1, 1, …
Аннотация: Размещения без повторений. Перестановки. Сочетания. Рекуррентные соотношения. Другой метод доказательства. Процесс последовательных разбиений. Задача: "Затруднение мажордома".
Размещения без повторений
Имеется различных предметов. Сколько из них можно составить -расстановок? При этом две расстановки считаются различными, если они либо отличаются друг от друга хотя бы одним элементом, либо состоят из одних и тех же элементов, но расположенных в разном порядке. Такие расстановки называют размещениями без повторений , а их число обозначают . При составлении -размещений без повторений из предметов нам надо сделать выборов. На первом шагу можно выбрать любой из имеющихся предметов. Если этот выбор уже сделан, то на втором шагу приходится выбирать из оставшихся предметов. На - м шагу предметов. Поэтому по правилу произведения получаем, что число -размещений без повторения из предметов выражается следующим образом:
Перестановки
При составлении размещений без повторений из элементов по мы получили расстановки, отличающиеся друг от друга и составом, и порядком элементов. Но если брать расстановки, в которые входят все элементов, то они могут отличаться друг от друга лишь порядком входящих в них элементов. Такие расстановки называют перестановками из n элементов , или, короче, - перестановками .
Сочетания
В тех случаях, когда нас не интересует порядок элементов в комбинации, а интересует лишь ее состав, говорят о сочетаниях. Итак, - сочетаниями из элементов называют всевозможные - расстановки, составленные из этих элементов и отличающиеся друг от друга составом, но не порядком элементов. Число -сочетаний, которое можно составить из элементов, обозначают через .
Формула для числа сочетаний получается из формулы для числа размещений. В самом деле, составим сначала все - сочетания из элементов, а потом переставим входящие в каждое сочетание элементы всеми возможными способами. При этом получается, что все -размещения из элементов, причем каждое только по одному разу. Но из каждого - сочетания можно сделать ! перестановок, а число этих сочетаний равно . Значит справедлива формула
Из этой формулы находим, что
Рекуррентные соотношения
При решении многих комбинаторных задач пользуются методом сведения данной задачи к задаче, касающейся меньшего числа предметов. Метод сведения к аналогичной задаче для меньшего числа предметов называется методом рекуррентных соотношений (от латинского "recurrere" - "возвращаться").
Понятие рекуррентных соотношений проиллюстрируем классической проблемой, которая была поставлена около 1202 года Леонардо из Пизы, известным как Фибоначчи. Важность чисел Фибоначчи для анализа комбинаторных алгоритмов делает этот пример весьма подходящим.
Фибоначчи поставил задачу в форме рассказа о скорости роста популяции кроликов при следующих предположениях. Все начинается с одной пары кроликов. Каждая пара становится фертильной через месяц, после чего каждая пара рождает новую пару кроликов каждый месяц. Кролики никогда не умирают, и их воспроизводство никогда не прекращается.
Пусть - число пар кроликов в популяции по
прошествии месяцев, и пусть эта популяция состоит из пар
приплода и "старых" пар, то есть . Таким образом, в очередном месяце произойдут следующие события: . Старая популяция в -й момент увеличится на число родившихся в момент времени . 
. Каждая старая пара в момент времени производит пару приплода в момент времени .
В последующий месяц эта картина повторяется:
Объединяя эти равенства, получим следующее рекуррентное соотношение:
| (7.1) |
Выбор начальных условий для последовательности чисел Фибоначчи не важен;
существенное свойство этой последовательности определяется рекуррентным
соотношением. Будем предполагать (иногда 
).
Рассмотрим эту задачу немного иначе .
Пара кроликов приносит раз в месяц приплод из двух крольчат (самки и самца), причем новорожденные крольчата через два месяца после рождения уже приносят приплод. Сколько кроликов появится через год, если в начале года была одна пара кроликов ?
Из условия задачи следует, что через месяц будет две пары кроликов. Через два месяца приплод даст только первая пара кроликов, и получится 3 пары. А еще через месяц приплод дадут и исходная пара кроликов, и пара кроликов, появившаяся два месяца тому назад. Поэтому всего будет 5 пар кроликов. Обозначим через количество пар кроликов по истечении месяцев с начала года. Ясно, что через месяцев будут эти пар и еще столько новорожденных пар кроликов, сколько было в конце месяца , то есть еще пар кроликов. Иными словами, имеет место рекуррентное соотношение
| (7.2) |
Так как, по условию, и , то последовательно находим
В частности, 
.
Числа называются числами Фибоначчи . Они обладают целым рядом замечательных свойств. Теперь выведем выражение этих чисел через . Для этого установим связь между числами Фибоначчи и следующей комбинаторной задачей.
Найти число последовательностей,состоящих из нулей и единиц, в которых никакие две единицы не идут подряд .
Чтобы установить эту связь , возьмем любую такую последовательность и сопоставим ей пару кроликов по следующему правилу: единицам соответствуют месяцы появления на свет одной из пар "предков" данной пары (включая и исходную), а нулями - все остальные месяцы. Например, последовательность 010010100010 устанавливает такую "генеалогию": сама пара появилась в конце 11-го месяца, ее родители - в конце 7-го месяца, "дед" - в конце 5-го месяца и "прадед" - в конце второго месяца. Исходная пара кроликов тогда зашифровывается последовательностью 000000000000.
Ясно, что при этом ни в одной последовательности не могут стоять две единицы подряд - только что появившаяся пара не может, по условию, принести приплод через месяц. Кроме того, при указанном правиле различным последовательностям отвечают различные пары кроликов, и обратно, две различные пары кроликов всегда имеют разную "генеалогию", так как, по условию, крольчиха дает приплод, состоящий только из одной пары кроликов.
Установленная связь показывает, что число -последовательностей, обладающих указанным свойством, равно .
Докажем теперь, что
| (7.3) |
Где , если нечетно, и , если четно. Иными словами, - целая часть числа (в
дальнейшем будем обозначать целую часть числа через ; таким образом, 
).
В самом деле, - это число всех - последовательностей из 0 и 1, в которых никакие две единицы не стоят рядом. Число же таких последовательностей, в которые входит ровно единиц и нулей, равно . Так как при этом должно выполняться
Рекуррентное соотношение имеет порядок k , если оно позволяет выразить f(n+k) через f(n), f(n+1), …, f(n+k-1).
Пример.
f(n+2)=f(n)f(n+1)-3f 2 (n+1)+1 – рекуррентное соотношение второго порядка.
f(n+3)=6f(n)f(n+2)+f(n+1) – рекуррентное соотношение третьего порядка.
Если задано рекуррентное соотношение k-го порядка, то ему могут удовлетворять бесконечно много последовательностей, так как первые k элементов последовательности можно задать произвольно – между ними нет никаких соотношений. Но если первые k членов заданы, то все остальные элементы определяются однозначно.
Пользуясь рекуррентным соотношением и начальными членами, можно один за другим выписывать члены последовательности, при этом рано или поздно мы получим любой её член. Однако если необходимо узнать только один определенный член последовательности, то нерационально вычислять все предыдущие. В этом случае удобнее иметь формулу для вычисления n-го члена.
Решением рекуррентного соотношения называется любая последовательность, для которой данное соотношение выполнено тождественно.
Пример . Последовательность 2, 4, 8, …, 2 n является решением для соотношения f(n+2)=3∙f(n+1) – 2∙f(n).
Доказательство . Общий член последовательности имеет вид f(n)=2 n . Значит, f(n+2)= 2 n+2, f(n+1)= 2n+1 . При любом n имеет место тождество 2 n+2 =3∙2 n+1 – 2∙2 n . Следовательно, при подстановке последовательности 2 n в формулу f(n+2)=3f(n+1) – 2f(n) соотношение выполняется тождественно. Значит, 2 n является решением указанного соотношения.
Решение рекуррентного соотношения k-го порядка называется общим , если оно зависит от k произвольных постоянных α 1 , α 2 , … α k и путем подбора этих постоянных можно получить любое решение данного соотношения.
Пример . Дано рекуррентное соотношение: f(n+2)=5f(n+1)-6f(n). Докажем, что его общее решение имеет вид: f(n)= α 2 n + β3 n .
1. Сначала докажем, что последовательность f(n)=α 2 n + β3 n является решением рекуррентного соотношения. Подставим данную последовательность в рекуррентное соотношение.
f(n)= α 2 n + β 3 n , значит, f(n+1)= (α 2 n+1 + β 3 n +1), f(n+2)= α 2 n+2 + β 3 n +2 , тогда
5f(n+1)-6f(n)=5∙(α 2 n+1 + β 3 n +1)-6∙(α 2 n + β 3 n)= α (5 2 n+1 –6 2 n)+ β (5 3 n +1 –6 3 n)= =α2 n ∙(10–6)+ β 3 n ∙(15 – 6)= α 2 n+2 + β 3 n +2 = f(n+2).
Рекуррентное соотношение выполняется, следовательно, α 2 n + β 3 n является решением данного рекуррентного соотношения.
2. Докажем, что любое решение соотношения f(n+2)=5f(n+1)–6f(n) можно записать в виде f(n)= α 2 n + β 3 n . Но любое решение рекуррентного соотношения второго порядка однозначно определяется значениями первых двух членов последовательности. Поэтому достаточно показать, что для любых а=f(1) и b=f(2) найдутся α и β такие, что 2 α +3 β =а и 4 α +9 β =b. Легко видеть, что система уравнений имеет решение для любых значений а и b.
Таким образом, f(n)= α 2 n + β 3 n является общим решением рекуррентного соотношения f(n+2)=5f(n+1)–6f(n).
Линейные рекуррентные соотношения с постоянными коэффициентами
Для решения рекуррентных соотношений общих правил нет, но существует часто встречающийся класс рекуррентных соотношений, для которых известен алгоритм их решения. Это – линейные рекуррентные соотношения с постоянными коэффициентами, т.е. соотношения вида:
f(n+k)=c 1 f(n+k-1)+c 2 f(n+k-2)+…+c k f(n).
Найдем решение общего линейного рекуррентного соотношения с постоянными коэффициентами первого порядка.
Линейное рекуррентное соотношение с постоянными коэффициентами первого порядка имеет вид: f(n+1)=c f(n).
Пусть f(1)=а, тогда f(2)=c∙f(1)=c∙a, f(3)=c∙f(2)=c 2 ∙a, аналогично f(4)=c 3 ∙a и так далее, заметим, что f(n)=c n -1 ∙f(1).
Докажем, что последовательность c n -1 ∙f(1) является решением рекуррентного соотношения первого порядка. f(n)=c n -1 ∙f(1), значит, f(n+1)=c n f(1). Подставляя это выражение в соотношение, получим тождество c n f(1)=с∙ c n -1 ∙f(1).
Рассмотрим теперь подробнее линейные рекуррентные соотношения с постоянными коэффициентами второго порядка , то есть соотношения вида
f(n+2)=C 1 ∙f(n+1)+C 2 ∙f(n). (*).
Заметим, что все рассуждения сохраняются и для соотношений более высокого порядка.
Свойства решений :
1) Если последовательность x n является решением (*), то и последовательность a∙x n тоже является решением.
Доказательство.
x n является решением (*), следовательно, выполняется тождество x n +2 =C 1 x n +1 +C 2 x n . Домножим обе части равенства на a. Получим a∙x n +2 =a∙(С 1 ∙x n +1 +С 2 ∙x n)= С 1 ∙a∙x n +1 +С 2 ∙a∙x n . Это означает, что ax n является решением (*).
2) Если последовательности x n и y n являются решениями (*), то и последовательность x n +y n тоже является решением.
Доказательство.
x n и y n являются решениями, следовательно, выполняются следующие тождества:
x n +2 =C 1 x n +1 +C 2 x n .
y n +2 =C 1 y n +1 +C 2 y n .
Выполним почленное сложение двух равенств:
x n +2 +y n +2 =С 1 ∙x n +1 +С 2 ∙x n + С 1 ∙y n +1 +С 2 ∙y n = С 1 ∙(x n +1 + y n +1)+С 2 ∙(x n +y n). Это означает, что x n +y n является решением (*).
3) Если r 1 является решением квадратного уравнения r 2 =С 1 r+С 2 , то последовательность (r 1) n является решением для соотношения (*).
r 1 является решением квадратного уравнения r 2 =С 1 r+С 2 , значит, (r 1) 2 =C 1 r 1 +C 2 . Помножим обе части равенства на (r 1) n . Получим
r 1 2 r 1 n =(С 1 r 1 +С 2) r n .
r 1 n +2 =С 1 r 1 n +1 +С 2 r 1 n .
Это означает, что последовательность (r 1) n является решением (*).
Из этих свойств вытекает способ решения линейных рекуррентных соотношений с постоянными коэффициентами второго порядка:
1. Составим характеристическое (квадратное) уравнение r 2 =С 1 r+С 2 . Найдём его корни r 1, r 2. Если корни различны, то общее решение имеет вид f(n)= ar 1 n +βr 2 n .
2. Найдём коэффициенты a и β. Пусть f(0)=a, f(1)=b. Система уравнений
имеет решение при любых а и b. Этими решениями являются
Задача. Найдем формулу для общего члена последовательности Фибоначчи.
Решение.
Характеристическое уравнение имеет вид х 2 =х+1 или х 2 -х-1=0, его корнями являются числа , значит, общее решение имеет вид f(n)= 
. Как нетрудно видеть, из начальных условий f(0)=0, f(1)=1 вытекает, что a=-b=1/Ö5, и, следовательно, общее решение последовательности Фибоначчи имеет вид:
.
Что удивительно, это выражение при всех натуральных значениях n принимает целые значения.
Числа Фибоначчи.
При решении многих комбинаторных задач применяют метод сведения данной задачи к задаче касающегося меньшего числа элементов. Например, можно вывести формулу для числа перестановок:
Отсюда видно, что всегда может быть сведён к факториалу от меньшего числа.
Хорошей иллюстрацией к построению рекуррентных соотношений является задача Фибоначчи. В своей книге в 1202 г. итальянский математик Фибоначчи привел следующую задачу. Пара кроликов приносит приплод раз в месяц двух крольчат (самку и самца), причём новорождённые крольчата через два месяца после рождения сами приносят приплод. Сколько кроликов появится через год, если в начале была одна пара кроликов.
Из условия задачи следует, что через месяц будет две пары кроликов, через два месяца приплод даст только первая пара кроликов, появившихся два месяца назад, поэтому всего будет 3 пары кроликов. Ещё через месяц будет уже 5 пар. И так далее.
Обозначим через количество пар кроликов по истечении месяцев с начала года. Тогда через месяц количество пар кроликов можно найти по формуле:
Эта зависимость называется рекуррентным соотношением . Слово «рекурсия» означает возврат назад (в нашем случае – возврат к предыдущим результатам).
По условию, и , тогда по соотношению имеем: , , и т.д., .
Определение 1: Числа называются числами Фибоначчи . Это – известная в математике последовательность чисел:
1, 1, 2, 3, 5, 8, 13, 21, ...
В этой последовательности каждое последующее число является суммой двух предыдущих чисел. И в рекуррентном соотношении также последующий член находится как сумма двух предыдущих членов.
Установим связь между числами Фибоначчи и комбинаторной задачей. Пусть требуется найти число - последовательностей, состоящих из нулей и единиц, в которых никакие две единицы не стоят подряд.
Возьмем любую такую последовательность и сопоставим ей пару кроликов по следующему правилу: единицам соответствуют месяцы появления на свет одной из пар «предков» данной пары (включая и исходную), а нулями – все остальные месяцы. Например, последовательность устанавливает такую «генеалогию» – сама пара появилась в конце 11-го месяца, ее родители в конце 7-го месяца, «дед» – в конце 5-го месяца, и «прадед» в конце 2-го месяца. Первоначальная пара шифруется последовательностью . Ни в одной последовательности две единицы не могут стоять подряд – только что появившаяся пара не может принести приплод через месяц. Очевидно, различным последовательностям отвечают различные пары и обратно.
Таким образом, число последовательностей с указанными свойствами, равно .
Теорема 1: Число находится как сумма биномиальных коэффициентов:. Если – нечетно, то . Если – четно, то . Иначе: – целая часть числа .
Доказательство: В самом деле, - число всех последовательностей из 0 и 1, в которых никакие две единицы не стоят рядом. Число таких последовательностей, содержащих ровно единиц и нулей, равно , при этом , тогда изменяется от 0 до . Применяя правило суммы, получаем данную сумму.
Это равенство можно доказать иначе. Обозначим:
Из равенства , следует, что . Кроме этого, ясно, что и . Так как обе последовательности и удовлетворяют рекуррентному соотношению , то , и .
Определение 2: Рекуррентное соотношение имеет порядок , если оно позволяет вычислять через предыдущих членов последовательности: .
Например, – рекуррентное соотношение второго порядка, а рекуррентное соотношение 3-го порядка. Соотношение Фибоначчи является соотношением второго порядка.
Определение 3:Решением рекуррентного соотношения является последовательность, удовлетворяющая этому соотношению.
Если задано рекуррентное соотношение ‑ го порядка, то ему удовлетворяют бесконечно много последовательностей, т.к. первые элементов можно задать произвольно. Но если первые элементов заданы, то остальные члены определяются однозначно.
Например, соотношению Фибоначчи кроме рассмотренной выше последовательности 1, 1, 2, 3, 5, 8, 13, 21, ..., могут удовлетворять также и другие последовательности. К примеру, последовательность 2, 2, 4, 8, 12,... строится по тому же принципу. Но если задать начальные члены (их в последовательности Фибоначчи - 2), то решение определяется однозначно. Начальных членов берут столько, каков порядок соотношения.
По известным рекуррентным соотношениям и начальным членам можно выписывать члены последовательности один за другим и таким путем мы можем получить любой её член. Но во многих случаях, нам не нужны все предыдущие члены, а необходим один определенный член. В этом случае удобнее иметь формулу ‑ го члена последовательности.
Мы будем говорить, что некоторая последовательность является решением данного рекуррентного соотношения, если при подстановке этой последовательности соотношение тождественно выполняется.
Например, последовательность является одним из решений соотношения: . Это легко проверить обычной подстановкой.
Определение 4: Решение рекуррентного соотношения ‑ го порядка называется общим , если оно зависит от произвольных постоянных , меняя которые, можно получить любое решение данного соотношения.
Например, для соотношения общим решение будет .
В самом деле, легко проверяется, что оно будет решением нашего соотношения. Покажем, что любое решение можно получить в таком виде. Пусть и – произвольны.
Тогда найдутся такие и , что
Очевидно, для любых , система уравнений имеет единственное решение.
Определение 5: Рекуррентное соотношение называется линейным , если оно записывается в виде:
где - числовые коэффициенты.
Для решения произвольных рекуррентных соотношений общих правил, вообще говоря, нет. Однако для решения линейных рекуррентных соотношений есть общие правила решения.
Рассмотрим сначала соотношение 2-го порядка .
Решение этого соотношения основано на следующих утверждениях.
Теорема 2: Если и - являются решением данного рекуррентного соотношения 2-го порядка, то для любых чисел и последовательность также является решением этого соотношения.
Теорема 3: Если число является корнем квадратного уравнения , то последовательность является решением рекуррентного соотношения .
Из теорем 2, 3 вытекает следующее правило решения линейных рекуррентных соотношений 2-го порядка.
Пусть дано рекуррентное соотношение .
1) Составим квадратное уравнение , которое называется характеристическим для данного соотношения. Найдём все корни этого уравнения (даже кратные и комплексные).
2) Составим общее решение рекуррентного соотношения. Его структура зависит от вида корней (одинаковые они или различные).
а) Если это соотношение имеет два различных корня и , то общее решение соотношения имеет вид .
Действительно, из теорем 2, 3 следует, что - решение и система уравнений
Имеет единое решение, т.к. при условии .
Например, для чисел Фибоначчи, имеем . Характеристическое уравнение имеет вид: . Решая последнее уравнение, получим корни:, .
Если все корни характеристического уравнения различны, то общее решение имеет вид: .
Если же, например, , то этому корню соответствуют решения:
данного рекуррентного соотношения. В общем решении этому корню соответствует часть .
Например , решая рекуррентное соотношение:
составляем характеристическое уравнение вида: .
Его корни , . Поэтому общее решение есть.