В математике довольно часто используется метод сведения данной задачи к задаче с меньшим количеством предметов.

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

В математике довольно часто используется метод сведения данной задачи к задаче с меньшим количеством предметов.

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

Пользуясь рекуррентным соотношением можно свести задачу об n предметах к задаче об n-1 предметах, потом к задаче об n-2 предметах и т.д. Последовательно уменьшая число предметов, доходим до задачи, которую легко решить. Во многих случаях удается получить из рекуррентного соотношения явную формулу для решения задачи.

Пример. Задача Фибоначчи

В 1202 г. итальянский математик Фибоначчи сформулировал следующую задачу:

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

Решение.

N

Кол-во

Обозначим через F(n) – количество пар кроликов по истечении n месяцев с начала года. Видно, что через (n+1) месяцев будут эти F(n) пар и еще столько новорожденных пар кроликов сколько было в конце месяца (n-1), т.е. еще F(n-1) пар кроликов.

Т.о. справедливо рекуррентное соотношение

F(n+1) = F(n) + F(n-1)

Опр.ЧислаF(n) называют числами Фиббоначи.

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

Пример. Затруднение мажордома

Однажды мажордом короля Артура обнаружил, что к обеду за круглым столом приглашено 6 пар враждующих рыцарей. Сколькими способами их можно рассадить так, чтобы никакие два врага не сидели рядом?

Опр. Рекуррентным соотношением k-того порядка называется соотношение позволяющее выразить через .

Пример.

f(n+2) = f(n) f(n+1) - 3f²(n+1) +1 – рекуррентное соотношение 2-го порядка

f(n+3) = 6f(n) f(n+2) + f(n+1) – рекуррентное соотношение 3-го порядка

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

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

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

Пример.

Будет ли являться частным решением этого соотношения?

Следовательно, - частное решение рекуррентного соотношения.

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

Пример.

Будем искать решение в виде:

- характеристическое уравнение.

- частные решения.

- общее решение.

Найдем С₁ и С₂, используя начальные условия.

- формула общего члена последовательности Фибоначчи.

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

Доказательство.

Умножим первое равенство на А, второе на В и сложим вновь получившиеся равенства.

что и требовалось доказать

Лемма2. Если число х₁ является корнем характеристического уравнения (4), то последовательность 1, х₁, х₁², …, х₁^n-1,… является решением рекуррентного соотношения (3).

Доказательство.

1)

x²=px+q.

По лемме2, если - корни характеристического уравнения, то - решения рекуррентного соотношения (3). По лемме1 - также будет решением рекуррентного соотношения (3).

Подставим в (3) равенство , а также учтем, что по теореме Виета:

p=x₁+x₂, q= –x₁x₂:

То есть обращает в тождество уравнение (3).

Проверим, существуют ли такие C₁ и C₂.

Пусть f(0)=a, f(1)=b. Тогда:

Þ для любых a, b система имеет единственное решение Þ C₁ и C₂ можно найти Þ формула верна.

2)

по теореме Виета

Покажем, что будет решением рекуррентного соотношения.

То есть обращает в тождество уравнение (3). Проверим, существуют ли такие C₁ и C₂.

- общее решение, т.к. C₁ и C₂ можно найти.

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

В математике довольно часто используется метод сведения данной задачи к задаче с меньшим количеством предметов.

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

Пользуясь рекуррентным соотношением можно свести задачу об n предметах к задаче об n-1 предметах, потом к задаче об n-2 предметах и т.д. Последовательно уменьшая число предметов, доходим до задачи, которую легко решить. Во многих случаях удается получить из рекуррентного соотношения явную формулу для решения задачи.

Пример. Задача Фибоначчи

В 1202 г. итальянский математик Фибоначчи сформулировал следующую задачу:

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

Решение.

N

Кол-во

Обозначим через F(n) – количество пар кроликов по истечении n месяцев с начала года. Видно, что через (n+1) месяцев будут эти F(n) пар и еще столько новорожденных пар кроликов сколько было в конце месяца (n-1), т.е. еще F(n-1) пар кроликов.

Т.о. справедливо рекуррентное соотношение

F(n+1) = F(n) + F(n-1)

Опр.ЧислаF(n) называют числами Фиббоначи.

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

Пример. Затруднение мажордома

Однажды мажордом короля Артура обнаружил, что к обеду за круглым столом приглашено 6 пар враждующих рыцарей. Сколькими способами их можно рассадить так, чтобы никакие два врага не сидели рядом?

Опр. Рекуррентным соотношением k-того порядка называется соотношение позволяющее выразить через .

Пример.

f(n+2) = f(n) f(n+1) - 3f²(n+1) +1 – рекуррентное соотношение 2-го порядка

f(n+3) = 6f(n) f(n+2) + f(n+1) – рекуррентное соотношение 3-го порядка

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

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

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

Пример.

Будет ли являться частным решением этого соотношения?

Следовательно, - частное решение рекуррентного соотношения.

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

Пример.

Будем искать решение в виде:

- характеристическое уравнение.

- частные решения.

- общее решение.

Найдем С₁ и С₂, используя начальные условия.

- формула общего члена последовательности Фибоначчи.

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