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

       3.3 Случай равных корней характеристического уравнения

          Остановимся теперь на случае, когда оба корня характеристического
уравнения совпадают: r1 � r2 . В этом случае выражение C1 r1n �1 � C 2 r2n �1
уже не будет общим решением. Ведь из-за того, что r1 � r2 , это решение
можно записать в виде
                                   f �n � � �C1 � C 2 �r1n �1 � Cr1n �1 .
          У нас остается только одно произвольное постоянное C , и выбрать
его так, чтобы удовлетворить двум начальным условиям f �1� � a , f �2 � � b ,
вообще говоря, невозможно.
          Поэтому надо найти какое-нибудь второе решение отличное от
 f 1 �n � � r1n �1 . Оказывается, таким решением является f 2 �n � � nr1n �1 . В самом
деле, если квадратное уравнение r 2 � a1 r � a 2 имеет два совпадающих
корня r1 � r2 , то по теореме Виета a1 � 2r1 , a 2 � �r12 . Поэтому наше урав-
нение записывается так:
                                       r 2 � 2r1 r � r12 .
     Тогда рекуррентное соотношение имеет такой вид:
                       f �n � 2 � � 2r1 f �n � 1� � r12 f �n �.            (5)
      Проверим, что f 2 �n � � nr1n �1 действительно является его решением.
Имеем f 2 �n � 2 � � �n � 2 �r1n �1 , а f 2 �n � 1� � �n � 1�r1n . Подставляя эти значе-
ния в соотношение (4), получаем очевидное тождество
                              �n � 2 �r1n�1 � 2�n � 1�r1n �1 � nr1n�1 .
      Значит, nr1n �1 — решение нашего соотношения.
      Теперь уже знаем два решения f 1 �n � � r1n �1 и f 2 �n � � nr1n �1 заданного
соотношения. Его общее решение пишется так:
                    f �n � � C1 r1n �1 � C 2 nr1n �1 � rrn �1 �C1 � C 2 n � .
      Путем подбора C1 и C 2 можно удовлетворить любым начальным ус-
ловиям.
      Линейные рекуррентные соотношения с постоянными коэффициен-
тами, порядок которых больше двух, решаются таким же способом. Пусть
соотношение имеет вид
                      f �n � k � � a1 f �n � k � 1� � � � a k f �n � .
      Составляем характеристическое уравнение
                                  r k � a1 r k �1 � � � a k .
      Если все корни r1 ,� , rk этого алгебраического уравнения k -й степе-
ни различны, то общее решение имеет вид
                        f �n � � C1 r1n �1 � C 2 r2n �1 � � � C k rkn �1 .
                                          58