Дискретная математика. Элементы теории, задачи и упражнения. Часть 1. Булгакова И.Н. - 57 стр.

     Пусть дано рекуррентное соотношение
                        f (n � 2) � a1 f (n � 1) � a2 f (n).
     Составим квадратное уравнение
                                 r 2 � a1r � a2 ,                  (4)
которое называется характеристическим для данного соотношения.
Если это уравнение имеет два различных корня 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 ��      � � C2 �
                                             �      �
                                                           � .
                                                           �
                                      � 2 �         � 2 �




                                         57