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

k элементов последовательности можно задать совершенно произвольно –
между ними нет никаких соотношений. Но если первые k элементов зада-
ны, то все остальные элементы определяются совершенно однозначно –
элемент f �k � 1� выражается в силу рекуррентного соотношения через
 f �1�,� , f �k � , элемент f �k � 2 � – через f �2 �,� , f �k � 1� и т. д.
         Будем говорить, что некоторая последовательность является реше-
нием данного рекуррентного соотношения, если при подстановке этой по-
следовательности соотношение тождественно выполняется. Например, по-
следовательность
                                      2 , 4 ,8,� , 2 n ,�
является одним из решений рекуррентного соотношения
                                  f �n � 2 � � 3 f �n � 1� � 2 f �n � .
         В самом деле, общий член этой последовательности имеет вид
 f �n � � 2 n . Значит, f �n � 2 � � 2 n � 2 , f �n � 1� � 2 n �1 . Но при любом n имеет
место тождество 2 n � 2 � 3 � 2 n �1 � 2 � 2 n . Поэтому 2 n является решением ука-
занного соотношения.
          Решение рекуррентного соотношения k -го порядка называется об-
щим, если оно зависит от k произвольных постоянных C1 ,� , C k и путем
подбора этих постоянных можно получить любое решение данного соот-
ношения. Например, для соотношения
                          f �n � 2 � � 5 f �n � 1� � 6 f �n �                   (1)
общим решением будет
                                f �n � � C1 2 n � C 2 3 n .                     (2)
          В самом деле, легко проверить, что последовательность обращает
соотношение в тождество. Поэтому нам надо только показать, что любое
решение нашего соотношения можно представить в виде (2). Но любое
решение соотношения (1) однозначно определяется значениями f �1� и
 f �2 � . Пусть f �1� =a, f � 2 � =b . Поэтому нам надо доказать, что для любых
чисел a и b найдутся такие значения C1 и C 2 , что
                                          2C1 � 3C 2 � a
и
                                        2 2 C1 � 3 2 C 2 � b .
Но легко видеть, что при любых значениях a и b система уравнений
                                     �2C1 � 3C 2 � a ,
                                     �
                                     �4C1 � 9C 2 � b
имеет решение. Поэтому (2) действительно является общим решение соот-
ношения (1).



                                          55