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

     Если же, например, r1 � r2 � � � rs , то этому корню соответствуют
решения
        f 1 �n � � r1n �1 , f 2 �n � � nr1n �1 , f 3 �n � � n 2 r1n �1 ,� , f s �n � � n s �1 r1n �1
рассматриваемого рекуррентного соотношения. В общем решении этому
корню соответствует часть
                                  �
                          r1n �1 C1 � C 2 n � C 3 n 2 � � � C s n s �1 .�
     Составляя такие выражения для всех корней и складывая их, получа-
ем общее решение.
     Например, решим рекуррентное соотношение
                   f �n � 4 � � 5 f �n � 3� � 6 f �n � 2 � � 4 f �n � 1� � 8 f �n � .
     Характеристическое уравнение имеет здесь вид
                                 r 4 � 5r 3 � 6r 2 � 4r � 8 � 0 .
     Решая его, получаем корни
                                 r1 � 2 , r2 � 2 , r3 � 2 , r4 � �1.
     Значит, общее решение нашего соотношения имеет следующий вид:
                                            �                       �
                            f �n � � 2 n �1 C1 � C 2 n � C 3 n 2 � C 4 �� 1� .
                                                                                     n �1




                                ЗАДАЧИ И УПРАЖНЕНИЯ

       1. Написать первые пять членов решения рекуррентного соотноше-
ния f �n � 2 � � 2 f �n � 1� � 3 f �n � , удовлетворяющего заданным начальным
условиям:
   �� f �1� � 0       �� f �1� � �1        �� f �1� � 3        �� f �1� � 2       �� f �1� � 2
1) �             ; 2) �              ; 3) �               ; 4) �             ; 5) �            .
    � f � 2 � � 1      � f � 2 � � 1        � f � 2 � � 0       � f � 2 � � 1      � f � 2� � 8

     2. Проверить, являются ли данные функции решениями данных ре-
куррентных соотношений:

            f �n � 2 � � 2 f �n � 1� � f �n �;
       1)
            � 1 �n � � 5 � 2 n , � 2 �n � � 2n � 1, � 3 �n � � 3.

            f �n � 2 � � 4 f �n � 1� � 3 f �n �;
       2)
          � 1 �n � � 2n , � 2 �n � � 5 � 3 n � 1, � 3 �n � � 7
       3. Найти общее решение рекуррентных соотношений:
       1) f (n � 2) � 7 f (n � 1) � 12 f (n) � 0;
       2) f ( n � 2 ) � 3 f ( n � 1) � 10 f ( n ) � 0 ;
       3) f ( n � 2 ) � 4 f ( n � 1) � 13 f ( n ) � 0 ;

                                                    59