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

                                             46
Рекуррентные соотношения
       Пусть дано рекуррентное соотношение
                                f ( n +2 ) =a1 f ( n +1) +a2 f ( n ) .
Составим квадратное уравнение
                                       r 2 =a1r +a2 ,
которое называется характеристическим для данного соотношения. Ес-
ли это уравнение имеет два различных корня r1 и r2 , то общее решение
рекуррентного соотношения имеет вид
                        f ( n ) =C1 r1n −1 +C 2 r2n −2 .
         Действительно, по утверждению 2) f 1( n ) =r1n −1 и f 2 ( n ) =r2n −1 явля-
ются решениями нашего соотношения. По утверждению 1) и
 f ( n ) =C1 r1n −1 +C 2 r2n −2 является его решением. Надо показать, что любое
решение соотношения можно записать в этом виде. Но любое решение ли-
нейного рекуррентного соотношения второго порядка определяется значе-
ниями f ( 1) и f ( 2 ) . Поэтому достаточно показать, что система уравнений
                                       C1 +C 2 =a
                                       
                                       C1 r1 +C 2 r2 =b
имеет решение при любых a и b . Этими решениями являются
                                      b −ar2           ar −b
                                 C1 =         , C2 = 1        .
                                      r1 −r2           r1 −r2
Случай, когда оба корня уравнения r 2 =a1r +a2 совпадают друг с другом,
мы разберем несколько позже. Рассмотрим пример.
     При изучении чисел Фибоначчи мы пришли к рекуррентному соотно-
шению
                        f ( n ) = f ( n −1) + f ( n −2 ) .
Для него характеристическое уравнение имеет вид
                                    r 2 =r +1.
Корнями этого квадратного уравнения являются числа
                                1+ 5           1− 5
                          r1 =          , r1 =        .
                                  2               2
Поэтому общее решение соотношения Фибоначчи имеет вид
                                                n                 n
                                        1 + 5       1 − 5 
                           f ( n ) =C 1 
                                         2 
                                                +C 2 
                                                       2 .
                                                             
                                                          