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

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

уравнения совпадают:
21
rr
=
. В этом случае выражение
1
22
1
11
−−
+
nn
rCrC
уже не будет общим решением . Ведь из-за того , что
21
rr
=
, это решение
можно записать в виде
(
)
(
)
.CrrCCnf
nn 1
1
1
121
=−
=+=
У нас остается только одно произвольное постоянное
C
, и выбрать его
так, чтобы удовлетворить двум начальным условиям
(
)
(
)
bf,af
=
=
21 , во-
обще говоря, невозможно.
Поэтому надо найти какое-нибудь второе решение отличное от
(
)
1
11
−
=
n
rnf . Оказывается, таким решением является
(
)
1
12
−
=
n
nrnf . В самом
деле, если квадратное уравнение
21
2
arar += имеет два совпадающих
корня
21
rr
=
, то по теореме Виета
2
1211
2 ra,ra −==
. Поэтому наше урав-
нение записывается так:
2
11
2
2 rrrr −= .
Тогда рекуррентное соотношение имеет такой вид :
(
)
(
)
(
)
nfrnfrnf
2
11
122 −+=+ . (5)
Проверим, что
(
)
1
12
−
=
n
nrnf действительно является его решением . Имеем
(
)
(
)
1
12
22
+
+=+
n
rnnf
, а
(
)
(
)
n
rnnf
12
11 +=+
. Подставляя эти значения в со-
отношение (4), получаем очевидное тождество
(
)
(
)
1
1
1
1
1
1
122
+++
−+=+
nnn
nrrnrn .
Значит ,
1
1
−n
nr — решение нашего соотношения.
Теперь уже знаем два решения
(
)
1
11
−
=
n
rnf и
(
)
1
12
−
=
n
nrnf заданного
соотношения. Его общее решение пишется так:
(
)
(
)
nCCrnrCrCnf
n
r
nn
21
11
12
1
11
+=+=
−−−
.
Путем подбора
1
C и
2
C можно удовлетворить любым начальным услови-
ям .
Линейные рекуррентные соотношения с постоянными коэффициен -
тами, порядок которых больше двух, решаются таким же способом. Пусть
соотношение имеет вид
(
)
(
)
(
)
nfaknfaknf
k
+
+
−
+
=
+
K1
1
.
Составляем характеристическое уравнение
k
kk
arar ++=
−
K
1
1
.
Если все корни
k
r,,r K
1
этого алгебраического уравнение
k
- й степени раз-
личны, то общее решение имеет вид
(
)
11
22
1
11
−−−
+++=
n
kk
nn
rCrCrCnf K .
Если же, например,
s
rrr
=
=
=
K
21
, то этому корню соответствуют реше-
ния
(
)
(
)
(
)
(
)
1
1
11
1
2
3
1
12
1
11
−−−−−
====
ns
s
nnn
rnnf,,rnnf,nrnf,rnf K
рассматриваемого рекуррентного соотношения. В общем решении этому 
уравнения совпадают: 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 , во-
обще говоря, невозможно.
         Поэтому надо найти какое-нибудь второе решение отличное от
 f1 (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 — решение нашего соотношения.
      Теперь уже знаем два решения f1 (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 ) =C 1 r1n −1 +C 2 r2n −1 + +C k rkn −1 .
Если же, например, r1 =r2 = =rs , то этому корню соответствуют реше-
ния
         f1 (n ) =r1n −1 , f 2 (n ) =nr1n −1 , f 3 (n ) =n 2 r1n −1 , , f s (n ) =n s −1 r1n−1
рассматриваемого рекуррентного соотношения. В общем решении этому

Страницы