Часть II рекуррентные последовательности

И ПРОИЗВОДЯЩИЕ ФУНКЦИИ

Глава II

РЕКУРРЕНТНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ

И ПРОИЗВОДЯЩИЕ ФУНКЦИИ

Пусть – множество натуральных чисел. Если каждому натуральному числупоставлено в соответствие число, то говорят, что заданачисловая последовательность

, , …,, ….

Числа ,, … называютсячленами последовательности, число –общим членом последовательности, а натуральное число – егономером. Последовательность кратко обозначается .

Если числовая последовательность может быть задана при помощи формулы

,

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

Часто бывает удобно добавить к последовательности еще один элементи рассматривать последовательность

, ,, …,,…

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

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

§ 1. Рекуррентные последовательности

1. Определения и примеры. Обычно, когда собираются рассказать о рекуррентных последовательностях, приводят следующую задачу^:

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

Из условия задачи следует, что:

– через один месяц будет 2 пары кроликов (первая пара и ее приплод);

– через два месяца – 3 пары (приплод опять даст только первая пара);

– через три месяца – 5 пар (приплод дадут первая пара и достигшая двухмесячного возраста вторая);

– через четыре месяца – 8 пар (приплод дадут первая, вторая и третья пары) и т.д.

Количество пар кроликов, которое будет через n месяцев, обозначим через . Через месяц к этимпарам добавится еще столько новых пар, сколько было пар в конце-го месяца, т.е.пар. Отсюда следует, что

. (2.1.1)

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

Месяц (n)	1	2	3	4	5	6	7	8	9	10	11	12
Кол-во пар (un)	1	2	3	5	8	13	21	34	55	89	144	233

При желании эту таблицу можно продолжать сколько угодно. Полученная бесконечная последовательность

, ,, …,,, …

называется последовательностьюили рядом Фибоначчи, а ее члены – числами Фибоначчи. Заметим, что если в начале года взять пару только что народившихся кроликов, то тогда ,, и последовательность Фибоначчи будет иметь вид: