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

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

      При решении многих комбинаторных задач часто пользуются методом
сведения данной задачи к задаче, касающейся меньшего числа предметов.
Метод сведения к аналогичной задаче для меньшего числа предметов на-
зывается методом рекуррентных соотношений. Пользуясь рекуррентны-
ми соотношениями, можно свести задачу об n предметах к задаче об n −1
предметах, потом к задаче об n −2 предметах и т.д. Последовательно
уменьшая число предметов, доходим до задачи, которую уже легко решить.
      В книге “Liber Abaci” итальянский математик Фибоначчи среди мно-
гих других задач привел следующую: пара кроликов приносит раз в месяц
приплод из двух крольчат (самки и самца), причем новорожденные крольчата
через два месяца после рождения уже приносят приплод. Сколько кроликов
появится через год, если в начале года была одна пара кроликов?
      Из условия задачи следует, что через месяц будет две пары кроликов.
Через два месяца приплод даст только первая пара кроликов. Через два меся-
ца приплод даст только первая пара кроликов, и получится 3 пары. А еще че-
рез месяц приплод дадут и исходная пара, и пара кроликов, появившаяся два
месяца тому назад. Поэтому всего будет 5 пар кроликов.
      Обозначим через F( n ) количество пар кроликов по истечении n меся-
цев с начала года. Мы видим, что через n +1 месяцев будет F( n ) и еще
столько новорожденных пар кроликов, сколько было в конце месяца n −1 , то
есть еще F( n −1) пар кроликов. Иными словами, имеет место рекуррентное
соотношение
                           F( n +1) =F( n ) +F( n −1).
Так как по условию F( 0) =1 и F( 1) =2 , то последовательно находим
                     F( 2 ) =3 , F( 3) =5 , F( 4 ) =8 и т.д.
      Числа F( n ) называются числами Фибоначчи.



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

     Будем говорить, что рекуррентное соотношение имеет порядок k , если
оно позволяет выразить f (n +k ) через f (n ), f (n +1),Κ , f (n +k −1). Напри-
мер,
                   f (n +2 ) = f (n )f (n +1) −3 f 2 (n +1) +1
— рекуррентное соотношение второго порядка, а
                      f (n +3) =6 f (n )f (n +2 ) + f (n +1)
— рекуррентное соотношение третьего порядка.
     Если задано рекуррентное соотношение k -го порядка, то ему удовле-
творяет бесконечно много последовательностей. Дело в том, что первые k