Общим решением рекуррентного соотношения (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.

3. Линейные рекуррентные соотношения. Соотношение вида

a n + k +p 1 a n + k - 1 +…+p k a n =h (n ) (2)

где h (n ) – функция от числа , а , называется линейным рекуррентным соотношением .

Линейное рекуррентное соотношение называют однородным , если f (n )=0:

a n + k +p 1 a n + k - 1 +…+p k a n =0. (3)

Многочлен x k +p 1 x k - 1 +…+p k - 1 x +p k называется характеристическим для соотношения (2).

простым , если делится на , но не делится на .

Корень a многочлена называется кратным , если делится на , но не делится на , .

При этом число называется кратностью корня .

Основная теорема алгебры: многочлен степени с комплексными коэффициентами имеет комплексных корней с учетом их кратности.

Теорема 1 n простых корней a 1 , …, a n

, (4)

где c 1 ,…,c k ÎC .

Доказательство . Легко проверить следующие два утверждения.

(a ) Последовательность cx n , где c ÎC , является решением рекуррентного соотношения (3).

(b ) Если последовательности a n и b n являются решениями соотношения (3), то последовательность a n +b n также является решением соотношения (3).

Из (a ) и (b ) следует, что любая последовательность вида (4) является решением соотношения (3).

Обратно, любое решение соотношения (3) имеет вид (4).

При n =0,1,…,k -1, из равенства (4) мы получим систему линейных уравнений относительно c 1 ,…,c k :

(5)

Определитель системы (5) есть известный в алгебре определитель Вандермонда:

.

Так как простые корни 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, …

Рекуррентным соотношением , рекуррентным уравнением или рекуррентной формулой называется соотношение вида , которое позволяет вычислять все члены последовательности
, если заданы ее первые k членов.

1. Формула
задает арифметическую прогрессию.

2. Формула
определяет геометрическую прогрессию.

3. Формула
задает последовательность чисел Фибоначчи .

В случае, когда рекуррентное соотношение линейно и однородно, т. е. выполняется соотношение вида

(p =const), последовательность
называется возвратной . Многочлен

называется характеристическим для возвратной последовательности
. Корни многочлена
называются характеристическими .

Множество всех последовательностей, удовлетворяющих данному рекуррентному соотношению, называется общим уравнением .

Описание общего уравнения соотношения (1) имеет аналоги с описанием решения обыкновенного дифференциального уравнения с постоянными коэффициентами.

Теорема 1. 1. Пусть - корень характеристического многочлена (2). Тогда последовательность
, где c – произвольная константа, удовлетворяет соотношению (1).

2. Если
- простые корни характеристического многочлена (2), то общее решение рекуррентного соотношения (1) имеет вид , где
- произвольные константы.

3. Если - корень кратности
характеристического многочлена (2), то общее решение рекуррентного соотношения (1) имеет вид
, где - произвольные константы.

Зная общее решение рекуррентного уравнения (1), по начальным условиям,
можно найти неопределенные постоянные и те самым получить решение уравнения (1) с данными начальными условиями.

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

Корням характеристического многочлена
являются числа
. Следовательно, по теореме 3.1. общее решение имеет вид
. Используя начальные условия, получаем систему

решая которую, находим
и
. Таким образом,
.

Рассмотрим неоднородное линейное рекуррентное уравнение

Пусть
- общее решение однородного уравнения (1), а
- частное (конкретное) решение неоднородного уравнения (3). Тогда последовательность
образует общее решение уравнения (3), и тем самым справедлива.

Теорема 2. Общее решение неоднородного линейного рекуррентного уравнения представляется в виде суммы общего решения соответствующего однородного линейного рекуррентного уравнения и некоторого частного решения неоднородного уравнения.

Таким образом, в силу теоремы 1. задача нахождения общего решения рекуррентного уравнения (3) сводится к нахождению некоторого частного решения.

В отдельных случаях имеются общие рецепты нахождения общего решения.

Если
(где ) не является характеристическим корнем, то, подставляя
в (3), получаем и отсюда
, т. е. частное решение можно задать формулой
.

Пусть
- многочлен степени r от переменной n , и число 1 не является характеристическим корнем. Тогда и частное решение следует искать в виде
. Подставляя многочлены в формулу (3), получаем

Сравнивая коэффициенты в левой и правой частях последнего равенства, получаем соотношения чисел , позволяющие эти числа определить.

Пример. Найти решение уравнения

(4)

с начальным условием
.

Рассмотрим характеристический многочлен
. Так как
и правая часть
уравнения (3) равна n +1, то частное решение будем искать в виде
. Подставляя в уравнение (4), получаем . Приравнивая коэффициенты в левой и правой частях последнего равенства, получаем систему

откуда находим
. Таким образом, частное решение уравнения (4) имеет вид
. По теореме 3.1. общее решение однородного уравнения
задается формулой
, и по теореме 3.2. получаем общее решение уравнения (4):
. Из начального условия
находим
, т. е. . Таким образом,
.

«Производящая функция является устройством, отчасти напоминающим мешок. Вместо того чтобы нести отдельно много предметов, что могло бы оказаться затруднительным, мы собираем их вместе, и тогда нам нужно нести лишь один предмет - мешок».
Д. Пойа

Введение

Математика делится на два мира - дискретный и непрерывный. В реальном мире есть место и для того и для другого, и часто к изучению одного явления можно подойти с разных сторон. В этой статье мы рассмотрим метод решения задач с помощью производящих функций - мостика ведущего из дискретного мира в непрерывный, и наоборот.

Идея производящих функций достаточно проста: сопоставим некоторой последовательности - дискретному объекту, степенной ряд g 0 + g 1 z + g 2 z 2 +… + g n z n +… - объект непрерывный, тем самым мы подключаем к решению задачи целый арсенал средств математического анализа. Обычно говорят, последовательность генерируется, порождается производящей функцией. Важно понимать, что это символьная конструкция, то есть вместо символа z может быть любой объект, для которого определены операции сложения и умножения.

История возникновения производящих функций

Известно, что начало методу производящих функций положил английский математик Абрахам де Муавр, а дальнейшему развитию и продолжению данного метода мы обязаны великому математику, имя которого Леонард Эйлер.

В 50-х годах XVIII века Эйлер решал следующую задачу: какие грузы можно взвесить с помощью гирь в 2 0 , 2 1 , 2 2 ,..., 2 n грамм и сколькими способами? При решении этой задачи он использовал никому неизвестный на то время метод производящих функций , которому и посвящена данная статья. К этой задаче мы вернёмся немного позже, после того как разберёмся более подробно с устройством производящих функций.

Метод производящих функций

Изучение этого мощного механизма позволяющего решать многие задачи, мы начнём с простенькой задачи: сколькими способами можно расположить в линию чёрные и белые шары, общее количество которых равно n?

Обозначим белый шар символом ○, чёрный - ●, T n - искомое количество расположений шаров. Символом Ø - обозначим нулевое количество шаров. Как и любое решение комбинаторной задачи начнём с тривиальных случаев:

Если n=1, то очевидно имеется 2 способа - взять либо белый шар ○, либо взять чёрный шар ●, таким образом, T 2 = 2.

Если n=2, то имеется 4 способа расположений: ○○, ○●, ●○, ●●.

Рассмотрим случай для n=3. Мы можем начать белым шаром и продолжить 4-мя комбинациями, описанными выше ○○○, ○○●, ○●○, ○●●, или же мы можем начать чёрным шаром и аналогично продолжить 4-мя шарами ●○○, ●○●, ●●○, ●●●.

В итоге количество шаров удвоилось, то есть T 3 = 2T 2 . Аналогично T 4 = 2T 3 , то есть, обобщая для всех n, получаем рекуррентное уравнение T n = 2T n-1 которое и является решением для данной задачи. Решение такого уравнения можно легко угадать - T n = 2 n (так как 2⋅2 n-1 = 2 n).

А что если у нас плохо с угадыванием? И что делать, если уравнение будет сложнее? А вообще причём здесь производящие функции?

«Просуммируем» все возможные комбинации расположений шаров:

G = Ø + ○ + ● + ○○ + ○● + ●○ + ●● + ○○○ + ○○● + ○●○ + ○●● + ●○○ + ●○● + ●●○ + ●●● +…

Вопрос о допустимости такой нелепой на первый взгляд суммы опустим. Будем складывать и умножать последовательности шаров. Со сложением всё понятно, но что значит умножить одну последовательность шаров на другую? Перемножив ○● на ●○ мы получим не что иное как ○●●○. Заметим, однако, что произведение шаров в отличие от произведения чисел не является коммутативным, так как ○●⋅●○ ≠ ●○⋅○●. Символ Ø - в произведении играет роль мультипликативной единицы, то есть Ø ⋅ ○○● = ○○● ⋅ Ø = ○○● и коммутирует с любой последовательностью шаров.

Производя с рядом G последовательность манипуляций, а именно вынося за скобки левый белый и чёрный шары

G = Ø + ○ (Ø + ○ + ● + ○○ + ○● + ●○ + ●● + ...) + ● (Ø + ○ + ● + ○○ + ○● + ●○ + ●● + ...) = Ø + ○G +●G

Получим уравнение G = Ø + ○G +●G.

Несмотря на то, что умножение некоммутативно, и мы фактически не различаем левое и правое деление, попробуем всё же «решить» это уравнение, на свой страх и риск. Получим,

Учитывая формулу суммы геометрической прогрессии , имеем

В этой сумме так же учтены все возможные варианты разбиения в точности по одному разу. Далее воспользуемся формулой бинома Ньютона: , где - число сочетаний из n по k. Тогда с учетом этого имеем:

Коэффициент при ○ k ● n-k равный числу сочетаний из n по k, показывает общее количество последовательностей из n шаров содержащих ○ шары в количеств k штук и ● шары в количестве n-k штук. Таким образом, общее количество расположений n шаров есть сумма по всем возможным значениям k. Как известно .

Эту формулу можно было получить непосредственно из заменив Ø на 1, а ○ и ● на z (в виду их равнозначности). Получим то есть коэффициент при z n равен 2 n .

Обсуждение метода

Так что же позволяет данному методу быть работоспособным при решении различных задач?

Алгоритм решения задачи можно описать примерно следующим образом: рассматривается некоторая бесконечная сумма, которая в конечном итоге представляет собой формальный степенной ряд G(z) = g 0 + g 1 z + g 2 z 2 +… + g n z n +… причем коэффициенты g k (не заданные в явном виде) - являются ключом к решению исходной задачи. То, что ряд является формальным, говорит о том, что z - является просто символом, то есть вместо него может быть любой объект: число, шар, кость домино и т.д. В отличие от степенных рядов в анализе формальным степенным рядам не придается числовых значений и, соответственно, нет смысла говорить о сходимости таких рядов для числовых аргументов.

G(z) = g 0 + g 1 z + g 2 z 2 +… + g n z n +… - называется производящей функцией для последовательности . Заметим, однако, что хотя G(z) - функция, это всё таки формальная запись, то есть мы не можем подставить вместо z любое значение z = z 0 , за исключением z = 0, так как G(0) = g 0 .

Затем производя различные преобразования с бесконечной суммой G(z) мы преобразуем её к замкнутому (компактному) виду. То есть у производящей функции есть 2 представления: бесконечное и замкнутое и, как правило, для решения задачи необходимо бесконечный вид преобразовать к замкнутому, а затем замкнутый вид разложить в степенной ряд, и тем самым получить значения для коэффициентов g k .

Отвечая на поставленный вначале вопрос можно сказать так: успех данного метода связан с возможностью записать производящую функцию в замкнутом виде. Так, например, производящая функция для последовательности <1, 1, 1, ..., 1> в бесконечном виде представляется как 1 + x + x 2 + x 3 + ..., а в замкнутом .

А теперь вооружившись знаниями, вернемся к задаче, которую решал Эйлер.

Итак, задача звучит следующим образом: какие грузы можно взвесить с помощью гирь в 2 0 , 2 1 , 2 2 ,..., 2 n грамм и сколькими способам?

Я не знаю, как долго Эйлер придумывал решение для этой задачи, но оно поражает своей неожиданностью. Посудите сами. Эйлер рассматривает произведение G(z) = (1+z)(1+z 2)(1+z 4)… которое после раскрытия скобок представляется в виде бесконечного ряда G(z) = 1 + g 1 z + g 2 z 2 + g 3 z 3 +….

Что же из себя представляют коэффициенты g k ? Каждый g k - это коэффициент при z k , а z k - получается как произведение каких-то одночленов z 2m , то есть g k - это в точности число разных представлений числа k в виде суммы некоторых из чисел 1, 2, 2 2 , 2 3 ,..., 2 m ,…. Другими словами g k - это число способов взвешивания груза в k грамм заданными гирями. Как раз то, что мы искали!

Следующий шаг Эйлера поражает не менее предыдущего. Он умножает обе части равенства на (1-z).

(1-z)G(z) = (1-z)(1+z)(1+z 2)(1+z 4)(1+z 8)…
(1-z)G(z) = (1-z2)(1+z 2)(1+z 4)(1+z 8)…
(1-z)G(z) = (1-z 4)(1+z 4)(1+z 8)…
(1-z)G(z) = 1

С одной стороны G(z) = 1 + g 1 z + g 2 z 2 + g 3 z 3 +… с другой стороны мы только что получили . Последнее равенство есть не что иное, как сумма геометрической прогрессии, которая равна . Сопоставляя эти два равенства, получаем g 1 = g 2 = g 3 =… = 1, то есть любой груз в k грамм можно взвесить гирями в 1, 2, 4, 8,… грамм притом единственным способом.

Решение рекуррентных соотношений

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

Начнем со всеми знакомой последовательностью чисел Фибоначчи. Каждый из нас знает её рекуррентный вид: F 0 = 0, F 1 = 1, F n = F n-1 + F n-2 , n ≥ 2. Однако не каждый знает вид этой формулы в замкнутом виде и это не удивительно, ведь она содержит иррациональное число(«золотое сечение») в своём составе.

Итак, имеем

F 0 = 0,
F 1 = 1,
F n = F n-1 + F n-2 , n ≥ 2

Умножим каждую строчку на z 0 , z 1 , ..., z n соответственно:

Z 0 ⋅ F 0 = 0,
z 1 ⋅ F 1 = z,
z n ⋅ F n = z n ⋅ F n-1 + z n ⋅ F n-2 , n ≥ 2

Просуммируем эти равенства:

Обозначим левую часть

Рассмотрим каждое из слагаемых в правой части:

Имеем следующее уравнение G(z) = z + z G(z) + z 2 G(z) решая которое относительно G(z) находим

Производящая функция для последовательности чисел Фибоначчи.

Разложим её на сумму простейших дробей, для этого найдем корни уравнения . Решая это простое квадратное уравнение, получаем: . Тогда нашу производящую функцию можно разложить следующим образом:

Следующим шагом является нахождение коэффициентов a и b. Для этого умножим дроби на общий знаменатель:

Подставляя в это уравнение значение z = z 1 и z = z 2 , находим

Напоследок немного преобразуем выражение для производящей функции

Теперь каждая из дробей представляет собой сумму геометрической прогрессии.

По формуле находим

Но ведь мы искали G(z) в виде . Отсюда делаем вывод, что

Эту формулу можно переписать в другом виде не используя «золотое сечение»:

Что достаточно трудно было ожидать, учитывая красивое рекуррентное уравнение.

Давайте запишем общий алгоритм решения рекуррентных уравнений, используя производящие функции. Он записывается в 4 шага:

Причина, по которой данный метод работает, заключается в том, что единая функция G(z) представляет всю последовательность g n и это представление допускает многие преобразования.

Прежде чем переходить к следующему примеру, рассмотрим 2 операции, совершаемые над производящими функциями, которые часто оказываются полезными.

Дифференцирование и интегрирование производящих функций

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

Пусть G = G(z) – производящая функция. Производной этой функции называется функция . Дифференцирование, очевидно, линейная операция, поэтому для того, чтобы понять, как оно действует на производящих функциях, достаточно посмотреть на его действие, на степенях переменной. Имеем

Тем самым, действие дифференцирования на произвольной производящей функции
G (z) = g 0 + g 1 z + g 2 z 2 + g 3 z 3 +… дает G΄(z) = g 1 + 2g 2 z + 3g 3 z 2 + 4g 4 z 3 +….

Интегралом называется функция

Операция дифференцирования обратна операции интегрирования:

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

Нетрудно заметить, что для функций, представимых в виде степенных рядов, формула для производной соответствует обычной. Формула для интеграла соответствует значению интеграла с переменным верхним пределом

Используя только что полученные знания о дифференцировании и интегрировании производящих функций, попробуем решить следующее рекуррентное уравнение:

G 0 = 1,
g 1 = 1,
g n = g n-1 + 2g n-2 + (-1) n

Будем следовать вышеописанному алгоритму. Первое условие алгоритма выполнено. Умножим обе части всех равенств на z в соответствующей степени и просуммируем:

Z 0 ⋅ g 0 = 1,
z 1 ⋅ g 1 = z,
z n ⋅ g n = z n ⋅ g n-1 + 2z n ⋅ g n-2 + (-1) n ⋅ z n

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

Попытаемся выразить правую часть через G(z). Рассмотрим каждое слагаемое:

Составляем уравнение:

Это и есть производящая функция для заданного рекуррентного уравнения. Раскладывая её на простейшие дроби (например, методом неопределенных коэффициентов или методом подстановки различных значений z), получаем:

Второе и третье слагаемые легко раскладываются в степенной ряд, а вот с первым придется чуть повозиться. Используя правило дифференцирования производящих функций имеем:

Собственно всё. Раскладываем каждое слагаемое в степенной ряд и получаем ответ:

С одной стороны мы искали G(z) в виде , с другой стороны .

Значит, .

Вместо заключения

Производящие функции нашли большое применение в математике, поскольку являются мощным оружием при решении многих практических задач, связанных, например, с перечислением, распределением и разбиением множеств объектов различной природы. Кроме того применение производящих функций позволяет доказать некоторые комбинаторные формулы, которые иначе получить очень трудно. Например, разложение функции в степенной ряд имеет вид , то есть справедливо равенство:

Возводя в квадрат обе части этого равенства получим

Приравнивая коэффициенты при x n в левой и правой частях, получаем

Эта формула имеет прозрачный комбинаторный смысл, но доказать её непросто. Еще в 80-е годы XX века появились публикации, посвященный этому вопросу.

Аннотация: Размещения без повторений. Перестановки. Сочетания. Рекуррентные соотношения. Другой метод доказательства. Процесс последовательных разбиений. Задача: "Затруднение мажордома".

Размещения без повторений

Имеется различных предметов. Сколько из них можно составить -расстановок? При этом две расстановки считаются различными, если они либо отличаются друг от друга хотя бы одним элементом, либо состоят из одних и тех же элементов, но расположенных в разном порядке. Такие расстановки называют размещениями без повторений , а их число обозначают . При составлении -размещений без повторений из предметов нам надо сделать выборов. На первом шагу можно выбрать любой из имеющихся предметов. Если этот выбор уже сделан, то на втором шагу приходится выбирать из оставшихся предметов. На - м шагу предметов. Поэтому по правилу произведения получаем, что число -размещений без повторения из предметов выражается следующим образом:

Перестановки

При составлении размещений без повторений из элементов по мы получили расстановки, отличающиеся друг от друга и составом, и порядком элементов. Но если брать расстановки, в которые входят все элементов, то они могут отличаться друг от друга лишь порядком входящих в них элементов. Такие расстановки называют перестановками из n элементов , или, короче, - перестановками .

Сочетания

В тех случаях, когда нас не интересует порядок элементов в комбинации, а интересует лишь ее состав, говорят о сочетаниях. Итак, - сочетаниями из элементов называют всевозможные - расстановки, составленные из этих элементов и отличающиеся друг от друга составом, но не порядком элементов. Число -сочетаний, которое можно составить из элементов, обозначают через .

Формула для числа сочетаний получается из формулы для числа размещений. В самом деле, составим сначала все - сочетания из элементов, а потом переставим входящие в каждое сочетание элементы всеми возможными способами. При этом получается, что все -размещения из элементов, причем каждое только по одному разу. Но из каждого - сочетания можно сделать ! перестановок, а число этих сочетаний равно . Значит справедлива формула

Из этой формулы находим, что

Рекуррентные соотношения

При решении многих комбинаторных задач пользуются методом сведения данной задачи к задаче, касающейся меньшего числа предметов. Метод сведения к аналогичной задаче для меньшего числа предметов называется методом рекуррентных соотношений (от латинского "recurrere" - "возвращаться").

Понятие рекуррентных соотношений проиллюстрируем классической проблемой, которая была поставлена около 1202 года Леонардо из Пизы, известным как Фибоначчи. Важность чисел Фибоначчи для анализа комбинаторных алгоритмов делает этот пример весьма подходящим.

Фибоначчи поставил задачу в форме рассказа о скорости роста популяции кроликов при следующих предположениях. Все начинается с одной пары кроликов. Каждая пара становится фертильной через месяц, после чего каждая пара рождает новую пару кроликов каждый месяц. Кролики никогда не умирают, и их воспроизводство никогда не прекращается.

Пусть - число пар кроликов в популяции по прошествии месяцев, и пусть эта популяция состоит из пар приплода и "старых" пар, то есть . Таким образом, в очередном месяце произойдут следующие события: . Старая популяция в -й момент увеличится на число родившихся в момент времени . . Каждая старая пара в момент времени производит пару приплода в момент времени . В последующий месяц эта картина повторяется:

Объединяя эти равенства, получим следующее рекуррентное соотношение:

(7.1)

Выбор начальных условий для последовательности чисел Фибоначчи не важен; существенное свойство этой последовательности определяется рекуррентным соотношением. Будем предполагать (иногда ).

Рассмотрим эту задачу немного иначе .

Пара кроликов приносит раз в месяц приплод из двух крольчат (самки и самца), причем новорожденные крольчата через два месяца после рождения уже приносят приплод. Сколько кроликов появится через год, если в начале года была одна пара кроликов ?

Из условия задачи следует, что через месяц будет две пары кроликов. Через два месяца приплод даст только первая пара кроликов, и получится 3 пары. А еще через месяц приплод дадут и исходная пара кроликов, и пара кроликов, появившаяся два месяца тому назад. Поэтому всего будет 5 пар кроликов. Обозначим через количество пар кроликов по истечении месяцев с начала года. Ясно, что через месяцев будут эти пар и еще столько новорожденных пар кроликов, сколько было в конце месяца , то есть еще пар кроликов. Иными словами, имеет место рекуррентное соотношение

(7.2)

Так как, по условию, и , то последовательно находим

В частности, .

Числа называются числами Фибоначчи . Они обладают целым рядом замечательных свойств. Теперь выведем выражение этих чисел через . Для этого установим связь между числами Фибоначчи и следующей комбинаторной задачей.

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

Чтобы установить эту связь , возьмем любую такую последовательность и сопоставим ей пару кроликов по следующему правилу: единицам соответствуют месяцы появления на свет одной из пар "предков" данной пары (включая и исходную), а нулями - все остальные месяцы. Например, последовательность 010010100010 устанавливает такую "генеалогию": сама пара появилась в конце 11-го месяца, ее родители - в конце 7-го месяца, "дед" - в конце 5-го месяца и "прадед" - в конце второго месяца. Исходная пара кроликов тогда зашифровывается последовательностью 000000000000.

Ясно, что при этом ни в одной последовательности не могут стоять две единицы подряд - только что появившаяся пара не может, по условию, принести приплод через месяц. Кроме того, при указанном правиле различным последовательностям отвечают различные пары кроликов, и обратно, две различные пары кроликов всегда имеют разную "генеалогию", так как, по условию, крольчиха дает приплод, состоящий только из одной пары кроликов.

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

Докажем теперь, что

(7.3)

Где , если нечетно, и , если четно. Иными словами, - целая часть числа (в дальнейшем будем обозначать целую часть числа через ; таким образом, ).

В самом деле, - это число всех - последовательностей из 0 и 1, в которых никакие две единицы не стоят рядом. Число же таких последовательностей, в которые входит ровно единиц и нулей, равно . Так как при этом должно выполняться

Рекуррентным соотношением (уравнением, рекуррентной формулой) называется соотношение вида

которое позволяет вычислить все члены последовательности a 0 ,a 1 , a 2 ,.., если заданы её первыеk членов.

k – порядок рекуррентного уравнения.

Примеры . 1)a n +1 = a n + d - арифметическая прогрессия.

2) a n +1 = q ∙ a n - геометрическая прогрессия.

3) a n +2 = a n + a n +1 - последовательность чисел Фибоначчи.

1.4.2. Решение линейного однородного рекуррентного уравнения

Вслучае, когда рекуррентное уравнение линейно и однородно, то есть выполняется соотношение вида

Последовательность a 0 , a 1 , a 2 ,.., удовлетворяющая данному уравнению называетсявозвратной .

Многочлен

называется характеристическим многочленом для возвратной последовательности .

Корни этого многочлена называются характеристическими. Множество всех последовательностей, удовлетворяющих рекуррентному уравнению (1) называется его общим решением.

Общее решение однородного линейного рекуррентного уравнения имеет аналогию с решением линейного дифференциального уравнения. А именно, справедливы теоремы.

Теорема 1 . Пусть - корень характеристического многочлена (2), тогда последовательность
, гдеc – производная константа, удовлетворяет уравнению (1).

Теорема 2 . Если
- простые корни характеристического многочлена (2), то общее решение рекуррентного уравнения (1) имеет вид:

где c 1 ,c 2 ,..,c k – произвольные константы.

Теорема 3 . Если - корень кратности (i = 1,2,..,s ) характеристического многочлена (2), то общее решение рекуррентного уравнения (1) имеет вид:

где c ij – произвольные константы.

Зная общее решение рекуррентного уравнения (1), по начальным условиям a 0 ,a 1 ,..,a k -1 , можно найти неопределенные постоянныеc ij , и тем самым получить частное уравнении (1) с данными условиями.

Пример . Найти последовательность {a n }, удовлетворяющую рекуррентному уравнению

Характеристический многочлен

1 (2).4.3. Решение линейного неоднородного рекуррентного уравнения

Рассмотрим линейное неоднородное рекуррентное уравнение

a n+k + p 1 a n+k-1 + … + p k a n = f(n), (n = 0, 1, 2,…) (3)

Пусть {b n } – общее решение однородного уравнения (1). {c n } – частное (конкретное) решение неоднородного уравнения (3).

Тогда последовательность {b n +c n } образует общее решение уравнения (3). Таким образом, справедлива теорема.

Теорема 4 . Общее решение линейного неоднородного рекуррентного уравнения представляется в виде суммы общего решения соответствующего линейного однородного рекуррентного уравнения и некоторого частного решении неоднородного уравнения.

В результате, задача нахождения общего решения неоднородного уравнения (3) сводится к нахождению его частного решения. В отдельных случаях имеются рецепты нахождении частного решения.

1) Если f (n ) = β n , (гдеβ не является корнем характеристического уравнения), то частное решение следует искать в видеc n = C β n . Тогда, подставляя его в (3), получаем:

В результате, частное решение задаётся формулой

2) Пусть f (n ) –многочлен степениr от переменнойn , и число 1 не является характеристическим корнем. Тогда и частное решение следует искать в виде

Подставляя c n в (3) вместоa n , получаем

Сравнивая коэффициенты левой и правой частей полученного равенства, найдём соотношения для чисел d i , позволяющие эти числа определить.

Пример . Найти решение рекуррентного уравнения

с начальным условием .

Решение. Рассмотрим характеристический многочлен данного рекуррентного уравнения

Его корень . Тогда по теореме 1 общее решение соответствующего однородного рекуррентного уравнения задаётся формулой , где – произвольная константа.

Так как , т.е. единица не является корнем характеристического многочлена, а правая часть есть многочлен первой степени, то частное решение неоднородного уравнения ищется в виде полинома первой степени с неопределёнными коэффициентами , где и – неизвестные коэффициенты. Подставив вместо в исходное уравнение, получим или . Приравнивая коэффициенты левой и правой части последнего равенства, получаем систему уравнений для определения неизвестных и .