Решение линейных рекуррентных. Open Library - открытая библиотека учебной информации

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

Последовательность удовлетворяет следующему соотношению где - некоторые числа. При заданных значениях формула (1) полностью определяет последовательность; каждый ее элемент, начиная с к-го, является линейной комбинацией предыдущих к элементов с коэффициентами поэтому формулу (1) называют линейным рекуррентным соотношением к-го порядка. Если положить можно переписать в виде ИЛИ Решение линейных рекуррентных уравнений Поставим задачу - перейти от рекуррентного задания последовательности к формуле, выражающей зависимость общего члена последовательности хп от его номера п. Для решения этой задачи введем в рассмотрение: - производящую функцию последовательности - характеристический многочлен - многочлен Отметим следующую связь между многочленами: при. Докажем, что F(t) является дробно-рациональной функцией. Действительно, где коэффициенты Cm определяются по коэффициентам а^ и первым к членам последовательности Итак,) - многочлен степени не выше к- 1; поэтому F(t) = - правильная рациональная дробь. Дальнейший ход наших выкладок будет следующим: мы представим F(t) в виде суммы простейших дробей, запишем разложения простейших дробей по степеням переменной t, после чего по виду полученного ряда для F(t) будет ясен характер зависимости хп от п. Пусть характеристический многочлен /(А) имеет s различных (комплексных) корней: Aj кратности Г|, ..., Ха кратности rs: Как известно из алгебры, разложение правильной рациональной дроби со знаменателем g(t) на простейшие дроби имеет вид где некоторые константы. Применив биномиальное разложение, получим Таким образом, или, поскольку - многочлен от п степени (при фиксированном j)> где - некоторый многочлен степени не выше Мы доказали, что обший член последовательности, удовлетворяющей линейному рекуррентному соотношению fc-ro порядка, имеет вид где для число - корень кратности г, характеристического многочлена рекуррентного соотношения, Р*(я) - многочлен степени, не превосходящей г, - 1. Конкретный вид указанных многочленов определяется первыми к членами последовательности: В частности, если все корни характеристи- ческого многочлена - простые (т.е. кратности 1), то последовательность (ж„) представима в виде суммы геометрических прогрессий: где Ci - некоторые константы. Рассмотрим несколько примеров. Пример 1. Последовательность чисел Фибоначчи задается соотношениями Составим характеристическое уравнение: формула общего члена: Коэффициенты С\ и Cj определим из -начальных условий»: . Решив систему двухуравнений с двумя неизвестными, получим окончательный результат: Пример 2. Найдем все последовательности, удовлетворяющие условию Характеристическое уравнение А2 - 2А4- 1 =0 имеет двукратный корень: Au = 1, поэтому общий член последовательности имеет вид: где константы о и 6 определяются первыми двумя членами последовательности. Таким образом, (х„) - арифметическая прогрессия. Этот результат можно было предвидеть, заметив, что соотношение (3) является характеристическим для арифметической прогрессии: каждый член последовательности, начиная со второго, есть среднее арифметическое его соседних членов. ПримерЗ. Найдем последовательность (z„), задаваемую соотношениями Разложим характеристический многочлен на множители: Вид n-го члена последовательности:. Константы а, Ь, с найдем из системы уравнений Ответ: Упражнения Решение линейных рекуррентных уравнений Правило произведения 1. Из города А в город Б ведут 5 дорог, а из города Б в город В - 7 дорог. Сколько есть различных маршрутов из города А в В через Б? 2. В меню столовой 3 первых, 5 вторых и 3 третьих блюда. Сколькими способами можно выбрать обед из трех блюд (первое, второе и третье)? 3. Сколько есть двузначных чисел, не содержащих цифр 4. Сколько есть двузначных чисел, не содержащих цифр Номер автомашины состоит из трех букв латинского алфавита (содержащего 26 букв) и трех цифр. Сколько можно составить различных номеров автомашин? 6. У рояля 88 клавиш. Сколькими способами можно извлечь последовательно 6 звуков? 7. Сколько натуральных делителей имеет число 8. Сколько натуральных делителей имеет число 9. Сколько есть пятизначных чисел, 1) оканчивающихся двумя семерками? 2) начинающихся с двух одинаковых цифр? 3) в каждом из которых нет одинаковых цифр? 4) в каждом из которых соседние цифры различны? 5) делящихся на 4 и не содержащих цифр 6) в записи которых есть одинаковые цифры? 7) в записи которых есть хотя бы одна четная цифра? Решение линейных рекуррентных уравнений 10. Сколько есть перестановок цифр в которых 1) цифра 3 занимает третье место, а цифра 5 - пятое? 2) цифра 1 следует непосредственно за цифрой 0? 3) цифра 0 занимает одно из первых трех мест, а цифра 1 - одно из последних четырех мест? 4) цифра 0 занимает одно из первых пяти мест, а цифра 1 - одно из первых трех мест? 5) между цифрами 0 и 1 стоят ровно три цифры? 6) цифра 0 расположена левее цифры 1? 7) цифра 1 расположена между цифрами 0 и 2? 8) хотя бы одна из первых трех цифр делится на 3? 11. Сколькими способами можно рассадить за десятью партами 10 мальчиков и 10 девочек так, чтобы за каждой партой сидели а) мальчик слева, а девочка справа? б) мальчик и девочка? 12. Сколькими способами можно прочитать слово ПАРУС, двигаясь вправо или вниз по каждой из следующих таблиц? Сколькими способами можно расставить на шахматной доске 8 одинаковых ладей так, чтобы никакие две из них не били друг друга? 14. Сколькими способами можно расставить на шахматной доске 8 одинаковых ладей так, чтобы они били все поля? Сочетания 15. Вычислить: 16. Найти число подмножеств X множества обладающих следующими свойствами: 5) множество X состоит из трех четных и двух нечетных чисел; 17. На окружности последовательно отмечены точки Сколько существует 1) хорд с концами в отмеченных точках; 2) треугольников с вершинами в отмеченных точках; 3) выпуклых четырехугольников с вершинами в отмеченных точках; 4) треугольников с вершинами в отмеченных точках, не имеющих обших точек с прямой А2Ая; 5) треугольников с вершинами в отмеченных точках, имеющих общие точки с прямой AiA}? 18. На окружности отмечено п точек. Точки соединяются всевозможными хордами; известно, что никакие три из них не пересекаются в одной точке внутри круга. Найти: 1) число точек пересечения хорд внутри круга; 2) количество частей, на которые хорды делят круг. 19. На прямой I отмечено 8 точек, а на параллельной ей прямой m точек. Сколько существует 1) треугольников с вершинами в отмеченных точках; 2) выпуклых четырехугольников с вершинами в отмеченных точках? 20. Две команды играют в волейбол до 4 побед. Сколько существует разных вариантов изменения счета в игре по партиям? 21. Сколькими способами можно разложить 4 белых и 3 черных шара по 6 различным ящикам? 22. Решить предыдущую задачу при дополнительном условии: ни один яшик не должен быть пустым. 23. Сколькими способами можно разложить 20 одинаковых шаров по 5 различным яшикам так, чтобы 1) в каждом ящике оказалось не менее двух шаров; 2) в каждом ящике оказалось не более 5 шаров; 3) оказалось не более двух пустых яшиков? 24. Найти коэффициент при г100 в разложении многочлена Дан квадрат. Каждая его сторона разбита на п равных частей. Через точки деления проведены прямые, параллельные сторонам. Сколько существует 1) прямоугольников; 2) квадратов, ограниченных проведенными линиями? 26. В правлении банка 7 человек. Каково должна быть минимальное число замков от сейфа и как следует распределить ключи меж^у членами правления (каждый член правления может получить ключи от нескольких замков), чтобы любое большинство сейф могло открыть, а любое меньшинство - не могло? 27. Каким числом способов можно прочитать слово «абракадабра», двигаясь вправо или вниз по таблице (с. 76)? На клетчатой бумаге нарисован прямоугольник ABCD, стороны которого лежат на линиях сетки, причем длина отрезка AD в к раз больше длины отрезка АВ (к - натуральное число). Рассматриваются всевозможные пути, проходящие по линиям сетки и кратчайшим образом ведущие из А в С. Доказать, что среди этих путей в к раз больше тех, у которых первое звено лежит на AD, чем тех, у которых первое звено лежит на АВ. 29. Изучите поведение последовательности (о*), где ак = С* (при фиксированном п), с точки зрения возрастания-убывания. 30. Имеется карточная колода из 52 карт. Каким числом способов можно раздать по 13 карт четырем игрокам? Полиномиальная формула 31. Найти коэффициент при хк в разложении многочленов: Комбинаторные тождества 32. С помощью формулы бинома Ньютона Решение линейных рекуррентных уравнений доказать следующие тождества: 33. С помощью комбинаторных рассуждений доказать: Формула яключения-исключения 34. На кафедре лингвистики работают 13 человек, причем каждый из них знает хотя бы один иностранный язык. Десять человек знают английский язык, семеро немецкий, шестеро - французский. Пятеро знают английский и немецкий, четверо - английский и французский, трое - немецкий и французский. Сколько человек знают 1) все три языка; 2) ровно два языка; 3) только английский язык? 35. 1) Показать, что количество натуральных чисел, делящихся на п и не превосходящих положительного числа х, равно 2) Сколько есть чисел, не превосходящих и не делящихся ни на ни на, ни на 3) Сколько есть четырехзначных чисел, не делящихся ни на, ни на, ни на 4) Сколько есть чисел, не превосходящих и не делящихся ни на одно из чисел 5) Показать, что если п = 30т, то количество натуральных чисел, не превосходящих п и не делящихся ни на одно из чисел равно. 36. Пусть. Показать, что простых чисел в множестве не больше восьми. 37. На каждой стороне треугольника А ВС отмечено по п точек, разбивающих ее на п + 1 равных частей. Рассмотрим всевозможные треугольники с вершинами в отмеченных точках (по одной на каждой стороне). Сколько среди этих треугольников таких, у которых ни одна из сторон не параллельна стороне треугольника ABC? 38. Сколько существует б-значных номеров (первые цифры могут быть и нулями) с суммой цифр 27? 39. В кошельке лежит по 20 монет достоинством в рублей. Сколькими способами можно из этих 60 монет выбрать к монет (к ^ 60)? Задача о беспорядках и встречах 40. С помощью рекуррентных соотношений найти число беспорядков Dn для 42. Сколькими способами можно расставить на шахматной доске 8 одинаковых ладей так, чтобы никакие две из них не били друг друга и чтобы ни одна ладья не стояла на главной диагонали? 43. Сколькими способами можно раскрасить клетки шахматной доски 8 х 8 в 8 цветов так, чтобы клетки, имеющие обшую сторону, были бы окрашены в разные цвета и чтобы в каждом горизонтальном ряду встречались все 8 цветов? 44. Две колоды карт, содержащие по 52 карты, тщательно тасуются, после чего сравниваются карта за картой. Какова вероятность того, что не будет ни одной пары совпадающих карт? 45. Для числа перестановок п элементов с А: встречами Dn,k доказать тождества: Случайным образом выбирается перестановка чисел 1,2..., п. Пусть £ - количество элементов, остающихся на своих местах. Найти математическое ожидание и дисперсию случайной величины 47. Секретарше нужно отправить п различных писем по п различным адресам. Она подписывает конверты и случайным образом вкладывает письма в конверты. Сколько в среднем писем дойдет до своего адресата? Производящие функции Найти производящие функции следующих последовательностей: Пусть - последовательности, - соответствующие производящие функции. Выразить А(х) через В(х) при следующих соотношениях между последовательностями: Пусть an = С?Ък. Доказать, что bn = Рекуррентные соотношения 64. Последовательность (a„) удовлетворяет соотношению уравнение имеет два различных ненулевых корня х, и х2. Доказать, что имеет место тождество для некоторых С| и с2, однозначно определяемых Найти формулу общего члена последовательности: 66. Найти количество n-значных чисел, состоящих из цифр, в которых первая и последняя, а также любые две соседние цифры различны. 67. Сколько существует раскрасок вершин n-угольника, если соседние вершины должны быть разного цвета, а всего имеется к цветов? 68. Пусть n-й член последовательности задается формулой. Доказать, что для последовательности имеет место рекуррентное соотношение а, где 69. Найти а, если 70. Найти число двоичных последовательностей длины 11, не содержащих единиц ни в каких трех соседних позициях. 71. Найти обшие решения рекуррентных соотношений: 72. Найти ап по рекуррентным соотношениям и начальным условиям: 1) Каждая точка пересечения хорд однозначно задается (неупорядоченной) четверкой точек - концов этих хорд. Будем последовательно проводить хорды. Пусть kt - число точек пересечения t"-й хорды с ранее проведенными. Этими точками «-я хорда делится на fc, + 1 отрезков, каждый из которых, в свою очередь, делит одну «старую» часть разбиения круга на две «новые». Изначально имелась одна часть. После проведения всех N хорд количество частей равно Осталось заметить, что N = а обшее количество точек пересечения хорд Решение линейных рекуррентных уравнений (согласно первому пункту данной задачи). Интересен ответ к задаче при Он "гаков: Физик из известного анекдота на основании первых пяти результатов заявил бы, что общий ответ - 2я"а число 31 возникло в результате погрешности эксперимента. . Составьте отношение. Подсчитайте двумя способами сумму мощностей всех подмножеств п-элементного множества. 3 при нечетном при четном п. . Решение. Пусть U - множество последовательностей (составленных из шести неотрицательных целых чисел с суммой 27; а для каждого i множество Ai С U состоит из таких последовательностей, в которых Для решения -Заметим,что | а пересечение трех и большего числа множеств Ai пусто. 41. Используйте оценку остаточного члена ряда из признака Лейбница. Указание. Обозначим через о„ число двоичных последовательностей длины п, удовлетворяющих условию задачи. Найдите начальные условия и рекуррентное соотношение для последовательности (оп).

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

которое позволяет вычислить все члены последовательности 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 общее решение соответствующего однородного рекуррентного уравнения задаётся формулой , где – произвольная константа.

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

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

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

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

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

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

Сочетания

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В самом деле, - это число всех - последовательностей из 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 принимает целые значения.