Дискретная математика. Азарнова Т.В - 43 стр.

UptoLike

Рекуррентные соотношения
43
Рекуррентные соотношения
При решении многих комбинаторных задач часто пользуются методом
сведения данной задачи к задаче, касающейся меньшего числа предметов.
Метод сведения к аналогичной задаче для меньшего числа предметов на-
зывается методом рекуррентных соот ношений.
Пользуясь рекуррентны-
ми соотношениями, можно свести задачу об
n
предметах к задаче об 1
n
предметах, потом к задаче об 2
n
предметах и т.д. Последовательно
уменьшая число предметов, доходим до задачи, которую уже легко решить.
В книгеLiber Abaci” итальянский математик Фибоначчи среди мно-
гих других задач привел следующую: пара кроликов приносит раз в месяц
приплод из двух крольчат (самки и самца), причем новорожденные крольчата
через два месяца после рождения уже приносят приплод. Сколько кроликов
появится через год, если в начале года была одна пара кроликов?
Из условия задачи следует, что через месяц будет две пары кроликов.
Через два месяца приплод даст только первая пара кроликов. Через два меся-
ца приплод даст только первая пара кроликов, и получится 3 пары. А еще че-
рез месяц приплод дадут и исходная пара, и пара кроликов, появившаяся два
месяца тому назад. Поэтому всего будет 5 пар кроликов.
Обозначим через
)n(F
количество пар кроликов по истечении
n
меся-
цев с начала года. Мы видим, что через 1
+
++
+n
месяцев будет
)n(F
и еще
столько новорожденных пар кроликов, сколько было в конце месяца 1
n
, то
есть еще
)n(F
1
пар кроликов. Иными словами, имеет место рекуррентное
соотношение
).n(F)n(F)n(F
11
+
++
+=
==
=+
++
+
Так как по условию 10
=
==
=)(F
и 21
=
==
=)(F
, то последовательно находим
845332
=
==
==
==
==
==
=
)(F,)(F,)(F
и т.д.
Числа
)n(F называются числами Фибоначчи
.
§ 1. Решение рекуррентных соотношений
Будем говорить, что рекуррентное соотношение имеет порядок
k
, если
оно позволяет выразить
()
knf
+
через
() ( ) ( )
11
++
knf,,nf,nf
Κ
. Напри-
мер,
( )()() ()
11312
2
+++=+
nfnfnfnf
рекуррентное соотношение второго порядка, а
()()()()
1263
+++=+
nfnfnfnf
рекуррентное соотношение третьего порядка.
Если задано рекуррентное соотношение
k
-го порядка, то ему удовле-
творяет бесконечно много последовательностей. Дело в том, что первые
k